oj.uz

Submission #413600

# Submission time Handle Problem Language Result Execution time Memory
413600 2021-05-29T03:59:19 Z shoemakerjo Event Hopping 2 (JOI21_event2) C++14
7 / 100
 385 ms 35848 KB 
#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 = 200010;

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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5016 KB Output is correct
3 Correct 4 ms 5024 KB Output is correct
4 Correct 349 ms 32572 KB Output is correct
5 Correct 360 ms 34596 KB Output is correct
6 Correct 351 ms 34816 KB Output is correct
7 Correct 339 ms 35192 KB Output is correct
8 Correct 353 ms 34548 KB Output is correct
9 Correct 385 ms 34664 KB Output is correct
10 Correct 349 ms 34820 KB Output is correct
11 Correct 344 ms 35236 KB Output is correct
12 Correct 313 ms 32820 KB Output is correct
13 Correct 292 ms 33036 KB Output is correct
14 Correct 306 ms 33160 KB Output is correct
15 Correct 295 ms 33576 KB Output is correct
16 Correct 224 ms 31008 KB Output is correct
17 Correct 224 ms 31596 KB Output is correct
18 Correct 228 ms 31864 KB Output is correct
19 Correct 211 ms 30624 KB Output is correct
20 Correct 234 ms 31164 KB Output is correct
21 Correct 219 ms 31620 KB Output is correct
22 Correct 215 ms 30840 KB Output is correct
23 Correct 218 ms 31216 KB Output is correct
24 Correct 222 ms 31704 KB Output is correct
25 Correct 256 ms 30888 KB Output is correct
26 Correct 254 ms 31168 KB Output is correct
27 Correct 253 ms 31628 KB Output is correct
28 Correct 196 ms 33004 KB Output is correct
29 Correct 192 ms 32116 KB Output is correct
30 Correct 185 ms 30836 KB Output is correct
31 Correct 192 ms 30680 KB Output is correct
32 Correct 194 ms 30824 KB Output is correct
33 Correct 272 ms 30564 KB Output is correct
34 Correct 264 ms 34420 KB Output is correct
35 Correct 260 ms 35048 KB Output is correct
36 Correct 248 ms 35848 KB Output is correct
37 Correct 279 ms 32376 KB Output is correct
38 Correct 280 ms 32616 KB Output is correct
39 Correct 291 ms 32724 KB Output is correct
40 Correct 287 ms 33012 KB Output is correct
41 Correct 291 ms 33036 KB Output is correct
42 Correct 187 ms 31628 KB Output is correct
43 Correct 277 ms 32608 KB Output is correct
44 Correct 289 ms 32668 KB Output is correct
45 Correct 283 ms 32660 KB Output is correct
46 Correct 265 ms 32632 KB Output is correct

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5032 KB Output is correct
2 Correct 4 ms 5028 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Incorrect 4 ms 5028 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5032 KB Output is correct
2 Correct 4 ms 5028 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Incorrect 4 ms 5028 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5016 KB Output is correct
3 Correct 4 ms 5024 KB Output is correct
4 Correct 349 ms 32572 KB Output is correct
5 Correct 360 ms 34596 KB Output is correct
6 Correct 351 ms 34816 KB Output is correct
7 Correct 339 ms 35192 KB Output is correct
8 Correct 353 ms 34548 KB Output is correct
9 Correct 385 ms 34664 KB Output is correct
10 Correct 349 ms 34820 KB Output is correct
11 Correct 344 ms 35236 KB Output is correct
12 Correct 313 ms 32820 KB Output is correct
13 Correct 292 ms 33036 KB Output is correct
14 Correct 306 ms 33160 KB Output is correct
15 Correct 295 ms 33576 KB Output is correct
16 Correct 224 ms 31008 KB Output is correct
17 Correct 224 ms 31596 KB Output is correct
18 Correct 228 ms 31864 KB Output is correct
19 Correct 211 ms 30624 KB Output is correct
20 Correct 234 ms 31164 KB Output is correct
21 Correct 219 ms 31620 KB Output is correct
22 Correct 215 ms 30840 KB Output is correct
23 Correct 218 ms 31216 KB Output is correct
24 Correct 222 ms 31704 KB Output is correct
25 Correct 256 ms 30888 KB Output is correct
26 Correct 254 ms 31168 KB Output is correct
27 Correct 253 ms 31628 KB Output is correct
28 Correct 196 ms 33004 KB Output is correct
29 Correct 192 ms 32116 KB Output is correct
30 Correct 185 ms 30836 KB Output is correct
31 Correct 192 ms 30680 KB Output is correct
32 Correct 194 ms 30824 KB Output is correct
33 Correct 272 ms 30564 KB Output is correct
34 Correct 264 ms 34420 KB Output is correct
35 Correct 260 ms 35048 KB Output is correct
36 Correct 248 ms 35848 KB Output is correct
37 Correct 279 ms 32376 KB Output is correct
38 Correct 280 ms 32616 KB Output is correct
39 Correct 291 ms 32724 KB Output is correct
40 Correct 287 ms 33012 KB Output is correct
41 Correct 291 ms 33036 KB Output is correct
42 Correct 187 ms 31628 KB Output is correct
43 Correct 277 ms 32608 KB Output is correct
44 Correct 289 ms 32668 KB Output is correct
45 Correct 283 ms 32660 KB Output is correct
46 Correct 265 ms 32632 KB Output is correct
47 Correct 4 ms 5032 KB Output is correct
48 Correct 4 ms 5028 KB Output is correct
49 Correct 4 ms 4940 KB Output is correct
50 Correct 5 ms 4940 KB Output is correct
51 Incorrect 4 ms 5028 KB Output isn't correct
52 Halted 0 ms 0 KB -