Submission #101997

---

Source Code Expand

#include<iostream>
#include<queue>
#include<map>
#include<algorithm>
#include<cstring>

#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> P2;

int main(){
  int n,m;
  P2 a[200100];
  int to[100100];

  cin >> n >> m;
  rep(i,n){
    cin >> a[i].fs.sc >> a[i].fs.fs, to[i] = i;
    if(a[i].fs.fs < a[i].fs.sc)a[i].fs.fs += m;
    a[i].sc  = i;
    a[i+n] = a[i];
    a[i+n].fs.fs += m; a[i+n].fs.sc += m;
  }

  sort(a,a+2*n);

  int pos = 1;
  rep(i,n){
    while(pos<i+n && a[pos].fs.sc < a[i].fs.fs)pos++;
    if(pos<i+n && a[pos].fs.fs-m <= a[i].fs.sc){
      to[a[i].sc] = a[pos].sc;
    }
  }

  int ans = 1;
  int d[100100];
  int vis[100100];
  memset(vis,0,sizeof(vis));
  memset(d,0,sizeof(d));

  rep(i,n){
    if(!vis[i]){
      int now = i;
      vis[now] = i+1;
      d[now] = 1;

      while(!vis[to[now]]){
	vis[to[now]] = i+1;
	d[to[now]] = d[now] + 1;
	now = to[now];
      }
      if(vis[now] == vis[to[now]])ans = max(ans,d[now]-d[to[now]]+1);
    }
  }
  cout << ans << endl;
}


  

Submission Info

Judge Result