提出 #311954

---

ソースコード 拡げる

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <numeric>
#define FOR(x, to) for (int x = 0; x < to; x++)

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<P, int> PP;

int N;
PP p[100005];

int dp[1000005];
vector< set<P> >  S(1000005);
int ans_idx;

bool is_update(set<P> &a, set<P> &b) {
	set<P>::iterator itr = a.begin();
	set<P>::iterator itr2= b.begin();
	while (itr != a.end()) {
		if ((*itr).first < (*itr2).first) {
			return true;
		} else if ((*itr).first == (*itr2).first) {
			if ((*itr).second < (*itr2).second) return true;
		}
		itr++;
		itr2++;
	}
	return false;
}

void debug(set<P> s) {
	set<P>::iterator itr = s.begin();
	while (itr != s.end()) {
		cout << (*itr).first << "  " << (*itr).second << endl;
		itr++;
	}
}

int main() {
	cin >> N;
	FOR(i, N) {
		int a, b;
		cin >> a >> b;
		p[i].first.first = b;
		p[i].first.second = a;
		p[i].second = i + 1;
		ans_idx = max(ans_idx, b);
	}
	sort(p, p + N);
	int j = 1;
	for (int i = 0; i < N; i++) {
		int tail = p[i].first.first;
		int head = p[i].first.second;
		int idx =  p[i].second;
		//cout << "tail " << tail << endl;
		while (j <= tail) {
			dp[j] = dp[j - 1];
			S[j] = S[j - 1];
			j++;
		}
		if (dp[tail] <  dp[head] + 1) {
			dp[tail] = dp[head] + 1;
			S[tail] = S[head];
			S[tail].insert(P(head, idx));
		} else if (dp[tail] == dp[head] + 1) {
			//cout << i << "daada" << endl;
			set<P> tmp(S[head]);
			tmp.insert(P(head, idx));
			if (is_update(tmp, S[tail])) {
				S[tail] = tmp;
			}
		}
		//cout << "aaa" << i << endl;
		//for (int i = 0; i <= ans_idx; i++) {
		//	cout << i << " ";
		//}
		//cout << endl;
		//for (int i = 0; i <= ans_idx; i++) {
		//	cout << dp[i] << " ";
		//}
		//cout << endl;
	}
	//for (int i = 0; i <= ans_idx; i++) {
	//	cout << "-----" << i << endl;
	//	debug(S[i]);
	//}
	cout << dp[ans_idx] << endl;
	set<P>::iterator itr = S[ans_idx].begin();
	vector<int> ans;
	while (itr != S[ans_idx].end()) {
		ans.push_back((*itr).second);
		itr++;
	}
	for (int i = 0; i < ans.size(); i++) {
		printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' ');
	}
	return 0;
}

提出情報

ジャッジ結果