Submission #413598

#	Time	Username	Problem	Language	Result	Execution time	Memory
413598		shoemakerjo	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	138 ms	47628 KiB

event2

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pp pair<pii, int>

const int maxn = 100010;

int N, K;
vector<pp> events;

int seg[maxn*4];

void up(int spot, int val, int ss = 0, int se = 2*N-1, int si = 0) {
	if (ss > se) return;
	if (ss == se) {
		seg[si] = max(seg[si], val);
		return;
	}
	int mid = (ss+se)/2;
	if (spot <= mid) {
		up(spot, val, ss, mid, si*2+1);
	}
	else {
		up(spot, val, mid+1, se, si*2+2);
	}
	seg[si] = max(seg[si*2+1], seg[si*2+2]);
}

int query(int qs, int qe, int ss = 0, int se = 2*N-1, int si = 0) {
	if (qs > se || qe < ss) return 0;
	if (qs <= ss && se <= qe) return seg[si];
	int mid = (ss+se)/2;
	return max(query(qs, qe, ss, mid, si*2+1), query(qs, qe, mid+1, se, si*2+2));
}

map<int, int> compress;
set<int> spots;
int lens[maxn];

int lefts[maxn], rights[maxn];

vector<int> lenlist[maxn];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> K;
	int a, b;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		events.push_back(pp(pii(a, b), i));
		spots.insert(a);
		spots.insert(b);
	
	}
	int index = 0;
	for (int val : spots) {
		compress[val] = index++;
	}
	sort(events.begin(), events.end());
	reverse(events.begin(), events.end());

	for (pp vp : events) {
		a = compress[vp.first.first];
		b = compress[vp.first.second];
		lefts[vp.second] = a;
		rights[vp.second] = b;
		int curval = query(b, 2*N-1);
		curval++;
		up(a, curval);
		lens[vp.second] = curval;
		lenlist[curval].push_back(vp.second);
	}

	set<int> active;
	int cend = 0;

	for (int i = N; i > K; i--) {
		for (int v : lenlist[i]) active.insert(v);
	}
	vector<int> res;
	for (int i = K; i > 0; i--) {
		for (int v : lenlist[i]) active.insert(v);
		if (active.size() == 0) {
			cout << -1 << endl;
			return 0;
		}
		while (true) {
			int cur = *(active.begin());

			active.erase(active.begin());

			if (lefts[cur] >= cend) {
				cend = rights[cur];
				res.push_back(cur);
				break;
			}
		}
	}
	sort(res.begin(), res.end());
	for (int v : res) {
		cout << v+1 << endl;
	}
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61