oj.uz

Submission #637983

# Submission time Handle Problem Language Result Execution time Memory
637983 2022-09-03T19:53:24 Z GusterGoose27 New Home (APIO18_new_home) C++11
100 / 100
 4818 ms 1048576 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 3e5;
const int MAXV = 1e8;
 
int n, k, q;
 
class event {
public:
	int time;
	bool type; // 0 update, 1 query
	bool start_or_end; // 0 start, 1 end. Only for updates
	int store_type; // update only
	int pos; // both
	int id; // query
	event(int tim, bool se, int tp, int p) {
		time = tim;
		type = 0;
		start_or_end = se;
		store_type = tp;
		pos = p;
	}
	event(int tim, int p, int i) {
		type = 1;
		time = tim;
		pos = p;
		id = i;
	}
};
 
bool operator<(event &a, event &b) {
	return (a.time == b.time) ? (a.type < b.type) : (a.time < b.time);
}
 
vector<event> events;
int answs[MAXN];
int cnt[MAXN];
int num_active = 0;
multiset<int> locs[MAXN];
 
class stree {
public:
	stree *l = nullptr;
	stree *r = nullptr;
	int mx[2];
	multiset<int> all_vals[2]; // only for lowest level
	stree() {
		mx[0] = mx[1] = 0;
	}
	int mxq(int lv, int rv, bool lr, int lp = 0, int rp = MAXV) {
		if (lp > rv || rp < lv) return 0;
		if (lp >= lv && rp <= rv) return mx[lr];
		int best = 0;
		int m = (lp+rp)/2;
		if (l) best = max(best, l->mxq(lv, rv, lr, lp, m));
		if (r) best = max(best, r->mxq(lv, rv, lr, m+1, rp));
		return best;
	}
	void update(int p, int v, bool lr, int lp = 0, int rp = MAXV) {
		if (lp == rp) {
			all_vals[lr].insert(v);
			mx[lr] = *(all_vals[lr].rbegin());
			return;
		}
		int m = (lp+rp)/2;
		if (p <= m) {
			if (!l) l = new stree();
			l->update(p, v, lr, lp, m);
		}
		else {
			if (!r) r = new stree();
			r->update(p, v, lr, m+1, rp);
		}
		mx[lr] = 0;
		if (l) mx[lr] = max(mx[lr], l->mx[lr]);
		if (r) mx[lr] = max(mx[lr], r->mx[lr]);
	}
	void deupdate(int p, int v, bool lr, int lp = 0, int rp = MAXV) {
		if (lp == rp) {
			all_vals[lr].erase(all_vals[lr].find(v));
			if (all_vals[lr].empty()) mx[lr] = 0;
			else mx[lr] = *(all_vals[lr].rbegin());
			return;
		}
		int m = (lp+rp)/2;
		if (p <= m) {
			if (!l) l = new stree();
			l->deupdate(p, v, lr, lp, m);
		}
		else {
			if (!r) r = new stree();
			r->deupdate(p, v, lr, m+1, rp);
		}
		mx[lr] = 0;
		if (l) mx[lr] = max(mx[lr], l->mx[lr]);
		if (r) mx[lr] = max(mx[lr], r->mx[lr]);
	}
};
 
stree *tree;
 
void make(int l, int r) {
	if (l == -1 && r == -1) return;
	if (l == -1) {
		tree->update(0, r, 0);
		return;
	}
	if (r == -1) {
		tree->update(MAXV, MAXV-l, 1);
		return;
	}
	int p1 = (l+r)/2;
	int p2 = (l+r+1)/2;
	int v1 = MAXV-l;
	int v2 = r;
	tree->update(p2, v2, 0);
	tree->update(p1, v1, 1);
}
 
void unmake(int l, int r) {
	if (l == -1 && r == -1) return;
	if (l == -1) {
		tree->deupdate(0, r, 0);
		return;
	}
	if (r == -1) {
		tree->deupdate(MAXV, MAXV-l, 1);
		return;
	}
	int p1 = (l+r)/2;
	int p2 = (l+r+1)/2;
	int v1 = MAXV-l;
	int v2 = r;
	tree->deupdate(p2, v2, 0);
	tree->deupdate(p1, v1, 1);
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> k >> q;
	tree = new stree();	
	for (int i = 0; i < n; i++) {
		int x, t, a, b;
		cin >> x >> t >> a >> b; t--;
		events.push_back(event(a, 0, t, x));
		events.push_back(event(b+1, 1, t, x));
	}
	for (int i = 0; i < q; i++) {
		int x, t; cin >> x >> t;
		events.push_back(event(t, x, i));
	}
	sort(events.begin(), events.end());
	for (event ev: events) {
		if (ev.type == 0) {
			int type = ev.store_type;
			if (ev.start_or_end == 0) {
				num_active += (cnt[type] == 0);
				cnt[type]++;
				if (locs[type].find(ev.pos) != locs[type].end()) {
					locs[type].insert(ev.pos);
					continue;
				}
				auto iter = locs[type].lower_bound(ev.pos);
				int r = -1;
				int l = -1;
				if (iter != locs[type].end()) r = *iter;
				if (iter != locs[type].begin()) {
					iter--;
					l = *iter;
				}
				unmake(l, r);
				locs[type].insert(ev.pos);
				make(l, ev.pos);
				make(ev.pos, r);
			}
			else {
				cnt[type]--;
				num_active -= (cnt[type] == 0);
				locs[type].erase(locs[type].find(ev.pos));
				if (locs[type].find(ev.pos) != locs[type].end()) continue;
				auto iter = locs[type].lower_bound(ev.pos);
				int r = -1;
				int l = -1;
				if (iter != locs[type].end()) r = *iter;
				if (iter != locs[type].begin()) {
					iter--;
					l = *iter;
				}
				make(l, r);
				unmake(l, ev.pos);
				unmake(ev.pos, r);
			}
		}
		if (ev.type == 1) {
			if (num_active < k) {
				answs[ev.id] = -1;
				continue;
			}
			answs[ev.id] = max(tree->mxq(0, ev.pos, 0)-ev.pos, tree->mxq(ev.pos, MAXV, 1)-MAXV+ev.pos);
		}
	}
	for (int i = 0; i < q; i++) cout << answs[i] << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 10 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 11 ms 16532 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 10 ms 15444 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 12 ms 16724 KB Output is correct
11 Correct 10 ms 15168 KB Output is correct
12 Correct 11 ms 16364 KB Output is correct
13 Correct 9 ms 14676 KB Output is correct
14 Correct 9 ms 15188 KB Output is correct
15 Correct 9 ms 15188 KB Output is correct
16 Correct 9 ms 15060 KB Output is correct
17 Correct 9 ms 15444 KB Output is correct
18 Correct 9 ms 15188 KB Output is correct
19 Correct 9 ms 15060 KB Output is correct
20 Correct 11 ms 15572 KB Output is correct
21 Correct 8 ms 14420 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 9 ms 14932 KB Output is correct
24 Correct 10 ms 15188 KB Output is correct
25 Correct 10 ms 15572 KB Output is correct
26 Correct 10 ms 15700 KB Output is correct
27 Correct 9 ms 14420 KB Output is correct
28 Correct 9 ms 15316 KB Output is correct
29 Correct 10 ms 15316 KB Output is correct
30 Correct 9 ms 14828 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 10 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 11 ms 16532 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 10 ms 15444 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 12 ms 16724 KB Output is correct
11 Correct 10 ms 15168 KB Output is correct
12 Correct 11 ms 16364 KB Output is correct
13 Correct 9 ms 14676 KB Output is correct
14 Correct 9 ms 15188 KB Output is correct
15 Correct 9 ms 15188 KB Output is correct
16 Correct 9 ms 15060 KB Output is correct
17 Correct 9 ms 15444 KB Output is correct
18 Correct 9 ms 15188 KB Output is correct
19 Correct 9 ms 15060 KB Output is correct
20 Correct 11 ms 15572 KB Output is correct
21 Correct 8 ms 14420 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 9 ms 14932 KB Output is correct
24 Correct 10 ms 15188 KB Output is correct
25 Correct 10 ms 15572 KB Output is correct
26 Correct 10 ms 15700 KB Output is correct
27 Correct 9 ms 14420 KB Output is correct
28 Correct 9 ms 15316 KB Output is correct
29 Correct 10 ms 15316 KB Output is correct
30 Correct 9 ms 14828 KB Output is correct
31 Correct 793 ms 258940 KB Output is correct
32 Correct 84 ms 19652 KB Output is correct
33 Correct 815 ms 259844 KB Output is correct
34 Correct 806 ms 245976 KB Output is correct
35 Correct 861 ms 265616 KB Output is correct
36 Correct 868 ms 269200 KB Output is correct
37 Correct 732 ms 253736 KB Output is correct
38 Correct 737 ms 256928 KB Output is correct
39 Correct 502 ms 247796 KB Output is correct
40 Correct 509 ms 253340 KB Output is correct
41 Correct 416 ms 140360 KB Output is correct
42 Correct 400 ms 140552 KB Output is correct
43 Correct 72 ms 21516 KB Output is correct
44 Correct 389 ms 140768 KB Output is correct
45 Correct 469 ms 141008 KB Output is correct
46 Correct 405 ms 140868 KB Output is correct
47 Correct 252 ms 113396 KB Output is correct
48 Correct 254 ms 123156 KB Output is correct
49 Correct 291 ms 132768 KB Output is correct
50 Correct 298 ms 126684 KB Output is correct
51 Correct 299 ms 135976 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3347 ms 549684 KB Output is correct
2 Correct 4705 ms 994012 KB Output is correct
3 Correct 1066 ms 93352 KB Output is correct
4 Correct 3040 ms 447812 KB Output is correct
5 Correct 4170 ms 944016 KB Output is correct
6 Correct 4484 ms 987072 KB Output is correct
7 Correct 1006 ms 93212 KB Output is correct
8 Correct 2528 ms 411412 KB Output is correct
9 Correct 2936 ms 706460 KB Output is correct
10 Correct 4089 ms 1034064 KB Output is correct
11 Correct 2527 ms 1014884 KB Output is correct
12 Correct 2713 ms 1007736 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4609 ms 940116 KB Output is correct
2 Correct 428 ms 47868 KB Output is correct
3 Correct 4818 ms 1048576 KB Output is correct
4 Correct 1209 ms 91052 KB Output is correct
5 Correct 3248 ms 587608 KB Output is correct
6 Correct 2834 ms 461892 KB Output is correct
7 Correct 4417 ms 1046472 KB Output is correct
8 Correct 4544 ms 1048576 KB Output is correct
9 Correct 1136 ms 92380 KB Output is correct
10 Correct 2856 ms 505732 KB Output is correct
11 Correct 3711 ms 839660 KB Output is correct
12 Correct 4549 ms 1024348 KB Output is correct
13 Correct 2184 ms 963100 KB Output is correct
14 Correct 2182 ms 967276 KB Output is correct
15 Correct 2554 ms 1001744 KB Output is correct
16 Correct 2998 ms 994212 KB Output is correct
17 Correct 3157 ms 1005248 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 10 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 11 ms 16532 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 10 ms 15444 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 12 ms 16724 KB Output is correct
11 Correct 10 ms 15168 KB Output is correct
12 Correct 11 ms 16364 KB Output is correct
13 Correct 9 ms 14676 KB Output is correct
14 Correct 9 ms 15188 KB Output is correct
15 Correct 9 ms 15188 KB Output is correct
16 Correct 9 ms 15060 KB Output is correct
17 Correct 9 ms 15444 KB Output is correct
18 Correct 9 ms 15188 KB Output is correct
19 Correct 9 ms 15060 KB Output is correct
20 Correct 11 ms 15572 KB Output is correct
21 Correct 8 ms 14420 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 9 ms 14932 KB Output is correct
24 Correct 10 ms 15188 KB Output is correct
25 Correct 10 ms 15572 KB Output is correct
26 Correct 10 ms 15700 KB Output is correct
27 Correct 9 ms 14420 KB Output is correct
28 Correct 9 ms 15316 KB Output is correct
29 Correct 10 ms 15316 KB Output is correct
30 Correct 9 ms 14828 KB Output is correct
31 Correct 793 ms 258940 KB Output is correct
32 Correct 84 ms 19652 KB Output is correct
33 Correct 815 ms 259844 KB Output is correct
34 Correct 806 ms 245976 KB Output is correct
35 Correct 861 ms 265616 KB Output is correct
36 Correct 868 ms 269200 KB Output is correct
37 Correct 732 ms 253736 KB Output is correct
38 Correct 737 ms 256928 KB Output is correct
39 Correct 502 ms 247796 KB Output is correct
40 Correct 509 ms 253340 KB Output is correct
41 Correct 416 ms 140360 KB Output is correct
42 Correct 400 ms 140552 KB Output is correct
43 Correct 72 ms 21516 KB Output is correct
44 Correct 389 ms 140768 KB Output is correct
45 Correct 469 ms 141008 KB Output is correct
46 Correct 405 ms 140868 KB Output is correct
47 Correct 252 ms 113396 KB Output is correct
48 Correct 254 ms 123156 KB Output is correct
49 Correct 291 ms 132768 KB Output is correct
50 Correct 298 ms 126684 KB Output is correct
51 Correct 299 ms 135976 KB Output is correct
52 Correct 184 ms 27188 KB Output is correct
53 Correct 163 ms 21928 KB Output is correct
54 Correct 518 ms 118520 KB Output is correct
55 Correct 361 ms 106820 KB Output is correct
56 Correct 305 ms 88892 KB Output is correct
57 Correct 392 ms 130464 KB Output is correct
58 Correct 400 ms 104812 KB Output is correct
59 Correct 325 ms 85924 KB Output is correct
60 Correct 395 ms 130360 KB Output is correct
61 Correct 139 ms 27664 KB Output is correct
62 Correct 193 ms 27408 KB Output is correct
63 Correct 353 ms 81776 KB Output is correct
64 Correct 419 ms 100244 KB Output is correct
65 Correct 468 ms 128044 KB Output is correct
66 Correct 444 ms 140384 KB Output is correct
67 Correct 251 ms 20520 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 10 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 11 ms 16532 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 10 ms 15444 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 12 ms 16724 KB Output is correct
11 Correct 10 ms 15168 KB Output is correct
12 Correct 11 ms 16364 KB Output is correct
13 Correct 9 ms 14676 KB Output is correct
14 Correct 9 ms 15188 KB Output is correct
15 Correct 9 ms 15188 KB Output is correct
16 Correct 9 ms 15060 KB Output is correct
17 Correct 9 ms 15444 KB Output is correct
18 Correct 9 ms 15188 KB Output is correct
19 Correct 9 ms 15060 KB Output is correct
20 Correct 11 ms 15572 KB Output is correct
21 Correct 8 ms 14420 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 9 ms 14932 KB Output is correct
24 Correct 10 ms 15188 KB Output is correct
25 Correct 10 ms 15572 KB Output is correct
26 Correct 10 ms 15700 KB Output is correct
27 Correct 9 ms 14420 KB Output is correct
28 Correct 9 ms 15316 KB Output is correct
29 Correct 10 ms 15316 KB Output is correct
30 Correct 9 ms 14828 KB Output is correct
31 Correct 793 ms 258940 KB Output is correct
32 Correct 84 ms 19652 KB Output is correct
33 Correct 815 ms 259844 KB Output is correct
34 Correct 806 ms 245976 KB Output is correct
35 Correct 861 ms 265616 KB Output is correct
36 Correct 868 ms 269200 KB Output is correct
37 Correct 732 ms 253736 KB Output is correct
38 Correct 737 ms 256928 KB Output is correct
39 Correct 502 ms 247796 KB Output is correct
40 Correct 509 ms 253340 KB Output is correct
41 Correct 416 ms 140360 KB Output is correct
42 Correct 400 ms 140552 KB Output is correct
43 Correct 72 ms 21516 KB Output is correct
44 Correct 389 ms 140768 KB Output is correct
45 Correct 469 ms 141008 KB Output is correct
46 Correct 405 ms 140868 KB Output is correct
47 Correct 252 ms 113396 KB Output is correct
48 Correct 254 ms 123156 KB Output is correct
49 Correct 291 ms 132768 KB Output is correct
50 Correct 298 ms 126684 KB Output is correct
51 Correct 299 ms 135976 KB Output is correct
52 Correct 3347 ms 549684 KB Output is correct
53 Correct 4705 ms 994012 KB Output is correct
54 Correct 1066 ms 93352 KB Output is correct
55 Correct 3040 ms 447812 KB Output is correct
56 Correct 4170 ms 944016 KB Output is correct
57 Correct 4484 ms 987072 KB Output is correct
58 Correct 1006 ms 93212 KB Output is correct
59 Correct 2528 ms 411412 KB Output is correct
60 Correct 2936 ms 706460 KB Output is correct
61 Correct 4089 ms 1034064 KB Output is correct
62 Correct 2527 ms 1014884 KB Output is correct
63 Correct 2713 ms 1007736 KB Output is correct
64 Correct 4609 ms 940116 KB Output is correct
65 Correct 428 ms 47868 KB Output is correct
66 Correct 4818 ms 1048576 KB Output is correct
67 Correct 1209 ms 91052 KB Output is correct
68 Correct 3248 ms 587608 KB Output is correct
69 Correct 2834 ms 461892 KB Output is correct
70 Correct 4417 ms 1046472 KB Output is correct
71 Correct 4544 ms 1048576 KB Output is correct
72 Correct 1136 ms 92380 KB Output is correct
73 Correct 2856 ms 505732 KB Output is correct
74 Correct 3711 ms 839660 KB Output is correct
75 Correct 4549 ms 1024348 KB Output is correct
76 Correct 2184 ms 963100 KB Output is correct
77 Correct 2182 ms 967276 KB Output is correct
78 Correct 2554 ms 1001744 KB Output is correct
79 Correct 2998 ms 994212 KB Output is correct
80 Correct 3157 ms 1005248 KB Output is correct
81 Correct 184 ms 27188 KB Output is correct
82 Correct 163 ms 21928 KB Output is correct
83 Correct 518 ms 118520 KB Output is correct
84 Correct 361 ms 106820 KB Output is correct
85 Correct 305 ms 88892 KB Output is correct
86 Correct 392 ms 130464 KB Output is correct
87 Correct 400 ms 104812 KB Output is correct
88 Correct 325 ms 85924 KB Output is correct
89 Correct 395 ms 130360 KB Output is correct
90 Correct 139 ms 27664 KB Output is correct
91 Correct 193 ms 27408 KB Output is correct
92 Correct 353 ms 81776 KB Output is correct
93 Correct 419 ms 100244 KB Output is correct
94 Correct 468 ms 128044 KB Output is correct
95 Correct 444 ms 140384 KB Output is correct
96 Correct 251 ms 20520 KB Output is correct
97 Correct 1229 ms 93224 KB Output is correct
98 Correct 425 ms 44396 KB Output is correct
99 Correct 4731 ms 1011832 KB Output is correct
100 Correct 1175 ms 66340 KB Output is correct
101 Correct 2821 ms 463968 KB Output is correct
102 Correct 4672 ms 1048576 KB Output is correct
103 Correct 4046 ms 996680 KB Output is correct
104 Correct 3894 ms 998392 KB Output is correct
105 Correct 2646 ms 987348 KB Output is correct
106 Correct 2911 ms 993596 KB Output is correct
107 Correct 2103 ms 414752 KB Output is correct
108 Correct 1884 ms 344908 KB Output is correct
109 Correct 2359 ms 507432 KB Output is correct
110 Correct 2203 ms 404916 KB Output is correct
111 Correct 2060 ms 328348 KB Output is correct
112 Correct 2413 ms 504124 KB Output is correct
113 Correct 725 ms 91852 KB Output is correct
114 Correct 1184 ms 93612 KB Output is correct
115 Correct 2292 ms 318472 KB Output is correct
116 Correct 2641 ms 390076 KB Output is correct
117 Correct 3025 ms 495892 KB Output is correct
118 Correct 2573 ms 541656 KB Output is correct
119 Correct 1750 ms 50244 KB Output is correct
120 Correct 1010 ms 374964 KB Output is correct
121 Correct 1292 ms 509056 KB Output is correct
122 Correct 1273 ms 513120 KB Output is correct
123 Correct 1364 ms 529952 KB Output is correct
124 Correct 1540 ms 532072 KB Output is correct
125 Correct 1432 ms 534348 KB Output is correct
126 Correct 1617 ms 490084 KB Output is correct