oj.uz

Submission #637978

# Submission time Handle Problem Language Result Execution time Memory
637978 2022-09-03T19:36:53 Z GusterGoose27 New Home (APIO18_new_home) C++11
47 / 100
 4388 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:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	int mx;
	multiset<int> all_vals; // only for lowest level
	stree(int lv, int rv) {
		mx = 0;
		lp = lv;
		rp = rv;
	}
	int mxq(int lv, int rv) {
		if (lp > rv || rp < lv) return 0;
		if (lp >= lv && rp <= rv) return mx;
		int best = 0;
		if (l) best = max(best, l->mxq(lv, rv));
		if (r) best = max(best, r->mxq(lv, rv));
		return best;
	}
	void update(int p, int v) {
		if (lp == rp) {
			all_vals.insert(v);
			mx = *(all_vals.rbegin());
			return;
		}
		int m = (lp+rp)/2;
		if (p <= m) {
			if (!l) l = new stree(lp, m);
			l->update(p, v);
		}
		else {
			if (!r) r = new stree(m+1, rp);
			r->update(p, v);
		}
		mx = 0;
		if (l) mx = max(mx, l->mx);
		if (r) mx = max(mx, r->mx);
	}
	void deupdate(int p, int v) {
		if (lp == rp) {
			all_vals.erase(all_vals.find(v));
			if (all_vals.empty()) mx = 0;
			else mx = *(all_vals.rbegin());
			return;
		}
		int m = (lp+rp)/2;
		if (p <= m) {
			if (!l) l = new stree(lp, m);
			l->deupdate(p, v);
		}
		else {
			if (!r) r = new stree(m+1, rp);
			r->deupdate(p, v);
		}
		mx = 0;
		if (l) mx = max(mx, l->mx);
		if (r) mx = max(mx, r->mx);
	}
};

stree *ltree, *rtree;

void make(int l, int r) {
	if (l == -1 && r == -1) return;
	if (l == -1) {
		ltree->update(0, r);
		return;
	}
	if (r == -1) {
		rtree->update(MAXV, MAXV-l);
		return;
	}
	int p1 = (l+r)/2;
	int p2 = (l+r+1)/2;
	int v1 = MAXV-l;
	int v2 = r;
	ltree->update(p2, v2);
	rtree->update(p1, v1);
}

void unmake(int l, int r) {
	if (l == -1 && r == -1) return;
	if (l == -1) {
		ltree->deupdate(0, r);
		return;
	}
	if (r == -1) {
		rtree->deupdate(MAXV, MAXV-l);
		return;
	}
	int p1 = (l+r)/2;
	int p2 = (l+r+1)/2;
	int v1 = MAXV-l;
	int v2 = r;
	ltree->deupdate(p2, v2);
	rtree->deupdate(p1, v1);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> k >> q;
	ltree = new stree(0, MAXV);
	rtree = new stree(0, MAXV);	
	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(ltree->mxq(0, ev.pos)-ev.pos, rtree->mxq(ev.pos, MAXV)-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 8 ms 14420 KB Output is correct
3 Correct 8 ms 14432 KB Output is correct
4 Correct 9 ms 14440 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 12 ms 17420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 11 ms 15956 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 12 ms 17828 KB Output is correct
11 Correct 10 ms 15592 KB Output is correct
12 Correct 11 ms 17120 KB Output is correct
13 Correct 8 ms 14824 KB Output is correct
14 Correct 10 ms 15636 KB Output is correct
15 Correct 10 ms 15572 KB Output is correct
16 Correct 9 ms 15324 KB Output is correct
17 Correct 9 ms 15956 KB Output is correct
18 Correct 10 ms 15636 KB Output is correct
19 Correct 9 ms 15316 KB Output is correct
20 Correct 10 ms 15956 KB Output is correct
21 Correct 8 ms 14436 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 11 ms 15292 KB Output is correct
24 Correct 11 ms 15588 KB Output is correct
25 Correct 10 ms 16156 KB Output is correct
26 Correct 11 ms 16212 KB Output is correct
27 Correct 9 ms 14548 KB Output is correct
28 Correct 9 ms 15700 KB Output is correct
29 Correct 10 ms 15700 KB Output is correct
30 Correct 9 ms 15060 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 8 ms 14420 KB Output is correct
3 Correct 8 ms 14432 KB Output is correct
4 Correct 9 ms 14440 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 12 ms 17420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 11 ms 15956 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 12 ms 17828 KB Output is correct
11 Correct 10 ms 15592 KB Output is correct
12 Correct 11 ms 17120 KB Output is correct
13 Correct 8 ms 14824 KB Output is correct
14 Correct 10 ms 15636 KB Output is correct
15 Correct 10 ms 15572 KB Output is correct
16 Correct 9 ms 15324 KB Output is correct
17 Correct 9 ms 15956 KB Output is correct
18 Correct 10 ms 15636 KB Output is correct
19 Correct 9 ms 15316 KB Output is correct
20 Correct 10 ms 15956 KB Output is correct
21 Correct 8 ms 14436 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 11 ms 15292 KB Output is correct
24 Correct 11 ms 15588 KB Output is correct
25 Correct 10 ms 16156 KB Output is correct
26 Correct 11 ms 16212 KB Output is correct
27 Correct 9 ms 14548 KB Output is correct
28 Correct 9 ms 15700 KB Output is correct
29 Correct 10 ms 15700 KB Output is correct
30 Correct 9 ms 15060 KB Output is correct
31 Correct 1103 ms 347812 KB Output is correct
32 Correct 78 ms 20548 KB Output is correct
33 Correct 1086 ms 350732 KB Output is correct
34 Correct 1069 ms 332068 KB Output is correct
35 Correct 1108 ms 356832 KB Output is correct
36 Correct 1076 ms 361844 KB Output is correct
37 Correct 862 ms 343172 KB Output is correct
38 Correct 852 ms 347556 KB Output is correct
39 Correct 581 ms 335508 KB Output is correct
40 Correct 661 ms 342968 KB Output is correct
41 Correct 517 ms 189304 KB Output is correct
42 Correct 499 ms 189672 KB Output is correct
43 Correct 63 ms 23836 KB Output is correct
44 Correct 531 ms 189960 KB Output is correct
45 Correct 485 ms 190128 KB Output is correct
46 Correct 460 ms 189784 KB Output is correct
47 Correct 283 ms 152452 KB Output is correct
48 Correct 293 ms 165788 KB Output is correct
49 Correct 326 ms 178988 KB Output is correct
50 Correct 362 ms 170708 KB Output is correct
51 Correct 338 ms 183388 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4388 ms 729368 KB Output is correct
2 Runtime error 3429 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3732 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14432 KB Output is correct
4 Correct 9 ms 14440 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 12 ms 17420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 11 ms 15956 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 12 ms 17828 KB Output is correct
11 Correct 10 ms 15592 KB Output is correct
12 Correct 11 ms 17120 KB Output is correct
13 Correct 8 ms 14824 KB Output is correct
14 Correct 10 ms 15636 KB Output is correct
15 Correct 10 ms 15572 KB Output is correct
16 Correct 9 ms 15324 KB Output is correct
17 Correct 9 ms 15956 KB Output is correct
18 Correct 10 ms 15636 KB Output is correct
19 Correct 9 ms 15316 KB Output is correct
20 Correct 10 ms 15956 KB Output is correct
21 Correct 8 ms 14436 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 11 ms 15292 KB Output is correct
24 Correct 11 ms 15588 KB Output is correct
25 Correct 10 ms 16156 KB Output is correct
26 Correct 11 ms 16212 KB Output is correct
27 Correct 9 ms 14548 KB Output is correct
28 Correct 9 ms 15700 KB Output is correct
29 Correct 10 ms 15700 KB Output is correct
30 Correct 9 ms 15060 KB Output is correct
31 Correct 1103 ms 347812 KB Output is correct
32 Correct 78 ms 20548 KB Output is correct
33 Correct 1086 ms 350732 KB Output is correct
34 Correct 1069 ms 332068 KB Output is correct
35 Correct 1108 ms 356832 KB Output is correct
36 Correct 1076 ms 361844 KB Output is correct
37 Correct 862 ms 343172 KB Output is correct
38 Correct 852 ms 347556 KB Output is correct
39 Correct 581 ms 335508 KB Output is correct
40 Correct 661 ms 342968 KB Output is correct
41 Correct 517 ms 189304 KB Output is correct
42 Correct 499 ms 189672 KB Output is correct
43 Correct 63 ms 23836 KB Output is correct
44 Correct 531 ms 189960 KB Output is correct
45 Correct 485 ms 190128 KB Output is correct
46 Correct 460 ms 189784 KB Output is correct
47 Correct 283 ms 152452 KB Output is correct
48 Correct 293 ms 165788 KB Output is correct
49 Correct 326 ms 178988 KB Output is correct
50 Correct 362 ms 170708 KB Output is correct
51 Correct 338 ms 183388 KB Output is correct
52 Correct 173 ms 30056 KB Output is correct
53 Correct 170 ms 24720 KB Output is correct
54 Correct 556 ms 156228 KB Output is correct
55 Correct 429 ms 142128 KB Output is correct
56 Correct 374 ms 117148 KB Output is correct
57 Correct 521 ms 175224 KB Output is correct
58 Correct 453 ms 139928 KB Output is correct
59 Correct 388 ms 113948 KB Output is correct
60 Correct 507 ms 175020 KB Output is correct
61 Correct 129 ms 29872 KB Output is correct
62 Correct 174 ms 30192 KB Output is correct
63 Correct 415 ms 106416 KB Output is correct
64 Correct 495 ms 132124 KB Output is correct
65 Correct 604 ms 171472 KB Output is correct
66 Correct 558 ms 189180 KB Output is correct
67 Correct 232 ms 21512 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14432 KB Output is correct
4 Correct 9 ms 14440 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 12 ms 17420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 11 ms 15956 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 12 ms 17828 KB Output is correct
11 Correct 10 ms 15592 KB Output is correct
12 Correct 11 ms 17120 KB Output is correct
13 Correct 8 ms 14824 KB Output is correct
14 Correct 10 ms 15636 KB Output is correct
15 Correct 10 ms 15572 KB Output is correct
16 Correct 9 ms 15324 KB Output is correct
17 Correct 9 ms 15956 KB Output is correct
18 Correct 10 ms 15636 KB Output is correct
19 Correct 9 ms 15316 KB Output is correct
20 Correct 10 ms 15956 KB Output is correct
21 Correct 8 ms 14436 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 11 ms 15292 KB Output is correct
24 Correct 11 ms 15588 KB Output is correct
25 Correct 10 ms 16156 KB Output is correct
26 Correct 11 ms 16212 KB Output is correct
27 Correct 9 ms 14548 KB Output is correct
28 Correct 9 ms 15700 KB Output is correct
29 Correct 10 ms 15700 KB Output is correct
30 Correct 9 ms 15060 KB Output is correct
31 Correct 1103 ms 347812 KB Output is correct
32 Correct 78 ms 20548 KB Output is correct
33 Correct 1086 ms 350732 KB Output is correct
34 Correct 1069 ms 332068 KB Output is correct
35 Correct 1108 ms 356832 KB Output is correct
36 Correct 1076 ms 361844 KB Output is correct
37 Correct 862 ms 343172 KB Output is correct
38 Correct 852 ms 347556 KB Output is correct
39 Correct 581 ms 335508 KB Output is correct
40 Correct 661 ms 342968 KB Output is correct
41 Correct 517 ms 189304 KB Output is correct
42 Correct 499 ms 189672 KB Output is correct
43 Correct 63 ms 23836 KB Output is correct
44 Correct 531 ms 189960 KB Output is correct
45 Correct 485 ms 190128 KB Output is correct
46 Correct 460 ms 189784 KB Output is correct
47 Correct 283 ms 152452 KB Output is correct
48 Correct 293 ms 165788 KB Output is correct
49 Correct 326 ms 178988 KB Output is correct
50 Correct 362 ms 170708 KB Output is correct
51 Correct 338 ms 183388 KB Output is correct
52 Correct 4388 ms 729368 KB Output is correct
53 Runtime error 3429 ms 1048576 KB Execution killed with signal 9
54 Halted 0 ms 0 KB -