Submission #1301912

---

Source Code Expand

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;

int a[100000], b[100000], c[1000001];
int dp[1000001];
int main() {
	int n; scanf("%d", &n);
	memset(c, -1, sizeof(c));
	rep(i, n) {
		scanf("%d%d", &a[i], &b[i]);
		c[b[i]] = max(c[b[i]], a[i]);
	}
	for (int i = 1000000; i > 0; i--) {
		dp[i - 1] = max(dp[i - 1], dp[i]);
		if (~c[i])dp[c[i]] = max(dp[c[i]], dp[i] + 1);
	}
	printf("%d\n", dp[0]);
	int s = 0;
	while (dp[s]) {
		if (s)printf(" ");
		rep(i, n) {
			if (s <= a[i] && dp[b[i]] == dp[s] - 1) {
				printf("%d", i + 1); s = b[i]; break;
			}
		}
	}
	puts("");
}

Submission Info

Judge Result