Submission #101848

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

#define rep(i, n) for(int i=0; i<int(n); i++)
#define mp make_pair

#define MAX_N 100010
#define MAX_LOG_N 17

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

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] = mp(t[i], i);
		ps[N*2 + i] = mp(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);
	}

	printf("%d\n", res);
}

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

Submission Info

Judge Result