Submission #101836

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define mp make_pair
#define all(v) (v).begin(), (v).end()

using namespace std;
typedef pair<int, int> pii;

int main(){
	int N, M;
	scanf("%d %d\n", &N, &M);
	vector<int> s(N * 2), t(N * 2);
	for (int i = 0; i < N; ++i) {
		scanf("%d %d\n", &s[i], &t[i]);
	}

	for (int i = 0; i < N; ++i) {
		if (t[i] < s[i]) t[i] += M;
		s[N + i] = s[i] + M;
		t[N + i] = t[i] + M;
	}

	vector<pair<int, int> > ps(N * 4);
	for (int i = 0; i < N * 2; ++i) {
		ps[i] = make_pair(t[i], i);
		ps[N * 2 + i] = make_pair(s[i], N * 2 + i);
	}
	sort(ps.begin(), ps.end());

	int last = -1;
	vector<vector<int> > next(25, vector<int>(N * 2));
	for (int i = N * 4 - 1; 0 <= i; --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 < next.size(); ++k) {
		for (int i = 0; i < N * 2; ++i) {
			if (next[k][i] < 0)
				next[k + 1][i] = -1;
			else
				next[k + 1][i] = next[k][next[k][i]];
		}
	}


	int res = 0;
	for (int i = 0; i < N; ++i) {
		int tmp = 0, j = i;
		for (int k = next.size() - 1; 0 <= k; --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);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:15:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:18:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result