Submission #101827

---

Source Code Expand

#include<iostream>
#include<algorithm>

#define REP(i, b, n) for(int i = b; i <(int)n; i++)
#define rep(i, n) REP(i, 0, n)

using namespace std;

const int MAX_N = 100000+10, MAX_M= 1000000+10;
const int MAX_LOG_N = 22;

int s[MAX_N*2], t[MAX_N*2];
int N, M;

pair<int, int> ps[MAX_N*4];

int next[MAX_LOG_N][MAX_N*2];

void solve(){
  int res = 0;
  rep(i, N){
    if(t[i] < s[i])t[i] += M;
    s[N+i] = s[i]+M;
    t[N+i] = t[i] + M;
  }
  rep(i, N*2){
    ps[i] = make_pair(t[i], i);
    ps[N*2+i] = make_pair(s[i], N*2+i);
  }
  sort(ps, ps+N*4);
  int last = -1;
  for(int i = N*4-1; i>=0; i--){
    int id = ps[i].second;
    if(id < N*2){
      next[0][id] = last;
    }else{
      id -= N*2;
      if(last <0 || t[last]>t[id]){
	last = id;
      }
    }
  }
  for(int k = 0; k+1 < MAX_LOG_N; k++){
    rep(i, N*2){
      if(next[k][i] <0)next[k+1][i] = -1;
      else next[k+1][i] = next[k][next[k][i]];
    }
  }
  rep(i, N){
    int tmp = 0, j=i;
    for(int k = MAX_LOG_N-1; k>=0;k--){
      int j2 = next[k][j];
      if(j2>=0 && t[j2] <= s[i] + M){
	j = j2;
	tmp |= 1<<k;
      }
    }
    res = max(res, tmp+1);
  }
  cout << res << endl;
}

int main(){
  while(cin >> N >> M){
    rep(i, N){
      cin >> s[i] >> t[i];
    }
    solve();
  }
}

Submission Info

Judge Result