Submission #1294397

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, l[100009], r[100009], s[1000009], used[1000009], bit[1000009];
vector<pair<int, int>>F[1000005], G[1000005]; vector<int>H;
void add(int s, int x) { while (s <= n) { bit[s] += x; s += (s&-s); } }
int sum(int s) { int x = 0; while (s >= 1) { x += bit[s]; s -= (s&-s); }return x; }
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> l[i] >> r[i];
		F[r[i]].push_back(make_pair(l[i], i));
		G[l[i]].push_back(make_pair(r[i], i));
	}
	s[0] = -1;
	for (int i = 1; i <= 1000000; i++) {
		s[i] = s[i - 1];
		for (int j = 0; j < (int)F[i].size(); j++) { s[i] = max(s[i], max(s[i - 1], F[i][j].first)); }
	}
	int R = 1000000; while (R != -1) { H.push_back(R); R = s[R]; }
	H.pop_back(); reverse(H.begin(), H.end());
	cout << H.size() << endl;
	int P = 0;
	for (int i = 0; i < H.size(); i++) {
		if (i)cout << ' ';
		for (int j = P + 1; j <= H[i]; j++) {
			for (int k = 0; k < F[j].size(); k++) {
				if (used[F[j][k].second] == 0) { add(F[j][k].second, 1); used[F[j][k].second] = 1; }
			}
		}
		int L = 0, R = n + 2, M, Q;
		while (true) {
			M = (L + R) / 2;
			int F1 = sum(M - 1), F2 = sum(M);
			if (F1 == 0 && F2 != 0) { cout << M; used[M] = 2; add(M, -1); Q = r[M]; break; }
			if (F2 == 0)L = M; else R = M;
		}
		for (int j = P; j < Q; j++) {
			for (int k = 0; k < G[j].size(); k++) {
				if (used[G[j][k].second] <= 1) {
					if (used[G[j][k].second] == 1)add(G[j][k].second, -1);
					used[G[j][k].second] = 2;
				}
			}
		}
		P = Q;
	}
	cout << endl;
	return 0;
}

Submission Info

Judge Result