oj.uz

Submission #853701

# Submission time Handle Problem Language Result Execution time Memory
853701 2023-09-25T03:55:45 Z flappybird New Home (APIO18_new_home) C++17
100 / 100
 3819 ms 417184 KB 
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long ll;
typedef pair<ll, ll> pll;
#define MAX 301010
#define MAXS 20
#define INF 1000000000
#define MOD (ll)1000000007
#define bb ' '
#define ln '\n'
template <typename T>
class Segment_Tree {
	//0-based index Segment Tree
	//O(N), O(lgN)
private:
	unsigned int N, s;
	vector<T> tree;
	vector<unsigned int> l, r;
	T query(unsigned int low, unsigned int high, unsigned int loc) {
		if (low == l[loc] && high == r[loc]) return tree[loc];
		if (high <= r[loc * 2]) return query(low, high, loc * 2);
		if (low >= l[loc * 2 + 1]) return query(low, high, loc * 2 + 1);
		return query(low, r[loc * 2], loc * 2) + query(l[loc * 2 + 1], high, loc * 2 + 1);
	}
	void _update(unsigned int loc, T val) {
		loc += s;
		tree[loc] = val;
		loc /= 2;
		while (loc) {
			tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
			loc /= 2;
		}
	}
	void init(unsigned int x = 1) {
		if (x >= s) {
			l[x] = r[x] = x - s;
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
		tree[x] = tree[x * 2] + tree[x * 2 + 1];
	}
public:
	Segment_Tree<T>() {
 
	}
	Segment_Tree<T>(vector<T>& v) {
		N = v.size();
		s = 1 << (unsigned int)ceil(log2(N));
		tree.resize(2 * s + 1);
		l.resize(2 * s + 1);
		r.resize(2 * s + 1);
		unsigned int i;
		for (i = 0; i < N; i++) tree[i + s] = v[i];
		init();
	}
	T query(unsigned int low, unsigned int high) { return query(low, high, 1); }
	void update(unsigned int location, T new_value) { _update(location, new_value); }
};
struct dat {
	ll x, t, a, b;
	dat() {}
	dat(ll x, ll t, ll a, ll b) :x(x), t(t), a(a), b(b) {}
	bool operator<(dat d) {
		if (t != d.t) return t < d.t;
		if (x != d.x) return x < d.x;
		if (a != d.a) return a < d.a;
		return b < d.b;
	}
};
struct Query {
	ll l, y, num;
	Query() {}
	Query(ll l, ll y, ll num) :l(l), y(y), num(num) {}
	bool operator<(Query q) {
		return y < q.y;
	}
};
map<ll, vector<dat>> arr;
multiset<ll> st[MAX];
vector<Query> query;
ll ans[MAX];
vector<ll> point, tarr;
vector<pll> larr;
vector<pair<ll, pair<ll, pll>>> qlog;
ll chk[MAX];
struct node {
	ll x, y;
	ll lv, rv;
	node() :x(0), y(0), lv(0), rv(-INF) {}
	node(ll x, ll y) :x(x), y(y) {
		lv = x + y;
		rv = y - x;
	}
	node(ll x, ll y, ll lv, ll rv) :x(x), y(y), lv(lv), rv(rv) {}
	node operator+(node x) { return node(0, 0, max(lv, x.lv), max(rv, x.rv)); }
};
bool operator<(pll p1, pll p2) {
	if (p1.first == p2.first) return p1.second < p2.second;
	return p1.first < p2.first;
}
ll getind(pll x) {
	return lower_bound(larr.begin(), larr.end(), x) - larr.begin();
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll N, K, Q;
	cin >> N >> K >> Q;
	ll i;
	ll x, t, a, b;
	vector<dat> datset;
	for (i = 1; i <= N; i++) {
		cin >> x >> t >> a >> b;
		arr[a].push_back(dat(x, t, a, b));
		arr[b + 1].push_back(dat(x, t, a, b));
		tarr.push_back(a);
		tarr.push_back(b + 1);
	}
	for (i = 0; i < Q; i++) {
		cin >> a >> b;
		query.push_back(Query(a, b, i));
	}
	sort(query.begin(), query.end());
	//simulation
	for (i = 1; i <= K; i++) st[i].insert(-INF);
	for (i = 1; i <= K; i++) st[i].insert(INF);
	map<ll, vector<dat>>::iterator it;
	for (it = arr.begin(); it != arr.end(); it++) {
		t = it->first;
		for (auto d : it->second) {
			ll pv = *prev(st[d.t].lower_bound(d.x));
			ll ne = *st[d.t].upper_bound(d.x);
			if (d.a == t) st[d.t].insert(d.x);
			else st[d.t].erase(st[d.t].find(d.x));
			larr.emplace_back(pv + ne, d.t);
			larr.emplace_back(pv + d.x, d.t);
			larr.emplace_back(d.x + ne, d.t);
		}
	}
	Segment_Tree<node> segtree;
	vector<node> v(larr.size());
	segtree = Segment_Tree<node>(v);
	it = arr.begin();
	ll cnt = 0;
	sort(larr.begin(), larr.end());
	larr.erase(unique(larr.begin(), larr.end()), larr.end());
	for (i = 0; i < Q; i++) {
		Query q = query[i];
		while (it != arr.end()) {
			ll t = it->first;
			if (t > q.y) break;
			for (auto d : it->second) {
				ll pv = *prev(st[d.t].lower_bound(d.x));
				ll ne = *st[d.t].upper_bound(d.x);
				if (d.a == t) {
					segtree.update(getind({ pv + ne, d.t }), node(pv + ne, 0));
					segtree.update(getind({ pv + d.x, d.t }), node(pv + d.x, d.x - pv));
					segtree.update(getind({ d.x + ne, d.t }), node(d.x + ne, ne - d.x));
					st[d.t].insert(d.x);
					if (!chk[d.t]) cnt++;
					chk[d.t]++;
				}
				else {
					st[d.t].erase(st[d.t].find(d.x));
					if (chk[d.t] == 1) cnt--;
					chk[d.t]--;
					if (st[d.t].find(d.x) != st[d.t].end()) continue;
					segtree.update(getind({ pv + ne, d.t }), node(pv + ne, ne - pv));
					segtree.update(getind({ pv + d.x, d.t }), node(pv + d.x, 0));
					segtree.update(getind({ d.x + ne, d.t }), node(d.x + ne, 0));
				}
			}
			it++;
		}
		if (cnt != K) {
			ans[q.num] = -1;
			continue;
		}
		node l = segtree.query(0, getind({ 2 * q.l, 10101010 }) - 1);
		node r = segtree.query(getind({ 2 * q.l, -1 }), larr.size() - 1);
		ans[q.num] = max(l.lv - 2 * q.l, r.rv + 2 * q.l) / 2;
	}
	for (i = 0; i < Q; i++) cout << ans[i] << ln;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 17084 KB Output is correct
5 Correct 4 ms 17636 KB Output is correct
6 Correct 5 ms 17752 KB Output is correct
7 Correct 5 ms 17756 KB Output is correct
8 Correct 4 ms 17628 KB Output is correct
9 Correct 5 ms 17756 KB Output is correct
10 Correct 5 ms 17496 KB Output is correct
11 Correct 6 ms 17500 KB Output is correct
12 Correct 5 ms 17524 KB Output is correct
13 Correct 6 ms 17644 KB Output is correct
14 Correct 5 ms 17500 KB Output is correct
15 Correct 5 ms 17500 KB Output is correct
16 Correct 5 ms 17756 KB Output is correct
17 Correct 6 ms 17500 KB Output is correct
18 Correct 5 ms 17608 KB Output is correct
19 Correct 5 ms 17756 KB Output is correct
20 Correct 5 ms 17696 KB Output is correct
21 Correct 4 ms 17624 KB Output is correct
22 Correct 5 ms 17756 KB Output is correct
23 Correct 5 ms 17620 KB Output is correct
24 Correct 5 ms 17752 KB Output is correct
25 Correct 6 ms 17500 KB Output is correct
26 Correct 5 ms 17500 KB Output is correct
27 Correct 6 ms 17756 KB Output is correct
28 Correct 5 ms 17500 KB Output is correct
29 Correct 4 ms 17500 KB Output is correct
30 Correct 4 ms 17500 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 17084 KB Output is correct
5 Correct 4 ms 17636 KB Output is correct
6 Correct 5 ms 17752 KB Output is correct
7 Correct 5 ms 17756 KB Output is correct
8 Correct 4 ms 17628 KB Output is correct
9 Correct 5 ms 17756 KB Output is correct
10 Correct 5 ms 17496 KB Output is correct
11 Correct 6 ms 17500 KB Output is correct
12 Correct 5 ms 17524 KB Output is correct
13 Correct 6 ms 17644 KB Output is correct
14 Correct 5 ms 17500 KB Output is correct
15 Correct 5 ms 17500 KB Output is correct
16 Correct 5 ms 17756 KB Output is correct
17 Correct 6 ms 17500 KB Output is correct
18 Correct 5 ms 17608 KB Output is correct
19 Correct 5 ms 17756 KB Output is correct
20 Correct 5 ms 17696 KB Output is correct
21 Correct 4 ms 17624 KB Output is correct
22 Correct 5 ms 17756 KB Output is correct
23 Correct 5 ms 17620 KB Output is correct
24 Correct 5 ms 17752 KB Output is correct
25 Correct 6 ms 17500 KB Output is correct
26 Correct 5 ms 17500 KB Output is correct
27 Correct 6 ms 17756 KB Output is correct
28 Correct 5 ms 17500 KB Output is correct
29 Correct 4 ms 17500 KB Output is correct
30 Correct 4 ms 17500 KB Output is correct
31 Correct 458 ms 99904 KB Output is correct
32 Correct 195 ms 85208 KB Output is correct
33 Correct 442 ms 97192 KB Output is correct
34 Correct 425 ms 97476 KB Output is correct
35 Correct 475 ms 99236 KB Output is correct
36 Correct 484 ms 99952 KB Output is correct
37 Correct 382 ms 96172 KB Output is correct
38 Correct 388 ms 97196 KB Output is correct
39 Correct 327 ms 96900 KB Output is correct
40 Correct 339 ms 96240 KB Output is correct
41 Correct 387 ms 96364 KB Output is correct
42 Correct 369 ms 97152 KB Output is correct
43 Correct 144 ms 89068 KB Output is correct
44 Correct 373 ms 97456 KB Output is correct
45 Correct 368 ms 96160 KB Output is correct
46 Correct 333 ms 97196 KB Output is correct
47 Correct 249 ms 95044 KB Output is correct
48 Correct 240 ms 95388 KB Output is correct
49 Correct 271 ms 95304 KB Output is correct
50 Correct 291 ms 95668 KB Output is correct
51 Correct 281 ms 95492 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1805 ms 338828 KB Output is correct
2 Correct 1948 ms 329784 KB Output is correct
3 Correct 1626 ms 364984 KB Output is correct
4 Correct 1728 ms 340864 KB Output is correct
5 Correct 1856 ms 326368 KB Output is correct
6 Correct 1932 ms 330804 KB Output is correct
7 Correct 1123 ms 361676 KB Output is correct
8 Correct 1371 ms 341624 KB Output is correct
9 Correct 1432 ms 333156 KB Output is correct
10 Correct 1655 ms 332560 KB Output is correct
11 Correct 1123 ms 324160 KB Output is correct
12 Correct 1154 ms 326680 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3024 ms 359720 KB Output is correct
2 Correct 1008 ms 319076 KB Output is correct
3 Correct 3250 ms 357296 KB Output is correct
4 Correct 2615 ms 389104 KB Output is correct
5 Correct 2496 ms 362936 KB Output is correct
6 Correct 2515 ms 366920 KB Output is correct
7 Correct 3116 ms 356536 KB Output is correct
8 Correct 3224 ms 354700 KB Output is correct
9 Correct 2351 ms 389120 KB Output is correct
10 Correct 2491 ms 364792 KB Output is correct
11 Correct 2717 ms 359376 KB Output is correct
12 Correct 2865 ms 355864 KB Output is correct
13 Correct 1456 ms 353808 KB Output is correct
14 Correct 1428 ms 349532 KB Output is correct
15 Correct 1684 ms 350436 KB Output is correct
16 Correct 1729 ms 356260 KB Output is correct
17 Correct 1700 ms 352024 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 17084 KB Output is correct
5 Correct 4 ms 17636 KB Output is correct
6 Correct 5 ms 17752 KB Output is correct
7 Correct 5 ms 17756 KB Output is correct
8 Correct 4 ms 17628 KB Output is correct
9 Correct 5 ms 17756 KB Output is correct
10 Correct 5 ms 17496 KB Output is correct
11 Correct 6 ms 17500 KB Output is correct
12 Correct 5 ms 17524 KB Output is correct
13 Correct 6 ms 17644 KB Output is correct
14 Correct 5 ms 17500 KB Output is correct
15 Correct 5 ms 17500 KB Output is correct
16 Correct 5 ms 17756 KB Output is correct
17 Correct 6 ms 17500 KB Output is correct
18 Correct 5 ms 17608 KB Output is correct
19 Correct 5 ms 17756 KB Output is correct
20 Correct 5 ms 17696 KB Output is correct
21 Correct 4 ms 17624 KB Output is correct
22 Correct 5 ms 17756 KB Output is correct
23 Correct 5 ms 17620 KB Output is correct
24 Correct 5 ms 17752 KB Output is correct
25 Correct 6 ms 17500 KB Output is correct
26 Correct 5 ms 17500 KB Output is correct
27 Correct 6 ms 17756 KB Output is correct
28 Correct 5 ms 17500 KB Output is correct
29 Correct 4 ms 17500 KB Output is correct
30 Correct 4 ms 17500 KB Output is correct
31 Correct 458 ms 99904 KB Output is correct
32 Correct 195 ms 85208 KB Output is correct
33 Correct 442 ms 97192 KB Output is correct
34 Correct 425 ms 97476 KB Output is correct
35 Correct 475 ms 99236 KB Output is correct
36 Correct 484 ms 99952 KB Output is correct
37 Correct 382 ms 96172 KB Output is correct
38 Correct 388 ms 97196 KB Output is correct
39 Correct 327 ms 96900 KB Output is correct
40 Correct 339 ms 96240 KB Output is correct
41 Correct 387 ms 96364 KB Output is correct
42 Correct 369 ms 97152 KB Output is correct
43 Correct 144 ms 89068 KB Output is correct
44 Correct 373 ms 97456 KB Output is correct
45 Correct 368 ms 96160 KB Output is correct
46 Correct 333 ms 97196 KB Output is correct
47 Correct 249 ms 95044 KB Output is correct
48 Correct 240 ms 95388 KB Output is correct
49 Correct 271 ms 95304 KB Output is correct
50 Correct 291 ms 95668 KB Output is correct
51 Correct 281 ms 95492 KB Output is correct
52 Correct 428 ms 105644 KB Output is correct
53 Correct 409 ms 104656 KB Output is correct
54 Correct 409 ms 101804 KB Output is correct
55 Correct 381 ms 99492 KB Output is correct
56 Correct 385 ms 101548 KB Output is correct
57 Correct 399 ms 97152 KB Output is correct
58 Correct 386 ms 98876 KB Output is correct
59 Correct 408 ms 100520 KB Output is correct
60 Correct 365 ms 97980 KB Output is correct
61 Correct 169 ms 94428 KB Output is correct
62 Correct 445 ms 106416 KB Output is correct
63 Correct 430 ms 102184 KB Output is correct
64 Correct 413 ms 101220 KB Output is correct
65 Correct 411 ms 97448 KB Output is correct
66 Correct 391 ms 96720 KB Output is correct
67 Correct 259 ms 84500 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 17084 KB Output is correct
5 Correct 4 ms 17636 KB Output is correct
6 Correct 5 ms 17752 KB Output is correct
7 Correct 5 ms 17756 KB Output is correct
8 Correct 4 ms 17628 KB Output is correct
9 Correct 5 ms 17756 KB Output is correct
10 Correct 5 ms 17496 KB Output is correct
11 Correct 6 ms 17500 KB Output is correct
12 Correct 5 ms 17524 KB Output is correct
13 Correct 6 ms 17644 KB Output is correct
14 Correct 5 ms 17500 KB Output is correct
15 Correct 5 ms 17500 KB Output is correct
16 Correct 5 ms 17756 KB Output is correct
17 Correct 6 ms 17500 KB Output is correct
18 Correct 5 ms 17608 KB Output is correct
19 Correct 5 ms 17756 KB Output is correct
20 Correct 5 ms 17696 KB Output is correct
21 Correct 4 ms 17624 KB Output is correct
22 Correct 5 ms 17756 KB Output is correct
23 Correct 5 ms 17620 KB Output is correct
24 Correct 5 ms 17752 KB Output is correct
25 Correct 6 ms 17500 KB Output is correct
26 Correct 5 ms 17500 KB Output is correct
27 Correct 6 ms 17756 KB Output is correct
28 Correct 5 ms 17500 KB Output is correct
29 Correct 4 ms 17500 KB Output is correct
30 Correct 4 ms 17500 KB Output is correct
31 Correct 458 ms 99904 KB Output is correct
32 Correct 195 ms 85208 KB Output is correct
33 Correct 442 ms 97192 KB Output is correct
34 Correct 425 ms 97476 KB Output is correct
35 Correct 475 ms 99236 KB Output is correct
36 Correct 484 ms 99952 KB Output is correct
37 Correct 382 ms 96172 KB Output is correct
38 Correct 388 ms 97196 KB Output is correct
39 Correct 327 ms 96900 KB Output is correct
40 Correct 339 ms 96240 KB Output is correct
41 Correct 387 ms 96364 KB Output is correct
42 Correct 369 ms 97152 KB Output is correct
43 Correct 144 ms 89068 KB Output is correct
44 Correct 373 ms 97456 KB Output is correct
45 Correct 368 ms 96160 KB Output is correct
46 Correct 333 ms 97196 KB Output is correct
47 Correct 249 ms 95044 KB Output is correct
48 Correct 240 ms 95388 KB Output is correct
49 Correct 271 ms 95304 KB Output is correct
50 Correct 291 ms 95668 KB Output is correct
51 Correct 281 ms 95492 KB Output is correct
52 Correct 1805 ms 338828 KB Output is correct
53 Correct 1948 ms 329784 KB Output is correct
54 Correct 1626 ms 364984 KB Output is correct
55 Correct 1728 ms 340864 KB Output is correct
56 Correct 1856 ms 326368 KB Output is correct
57 Correct 1932 ms 330804 KB Output is correct
58 Correct 1123 ms 361676 KB Output is correct
59 Correct 1371 ms 341624 KB Output is correct
60 Correct 1432 ms 333156 KB Output is correct
61 Correct 1655 ms 332560 KB Output is correct
62 Correct 1123 ms 324160 KB Output is correct
63 Correct 1154 ms 326680 KB Output is correct
64 Correct 3024 ms 359720 KB Output is correct
65 Correct 1008 ms 319076 KB Output is correct
66 Correct 3250 ms 357296 KB Output is correct
67 Correct 2615 ms 389104 KB Output is correct
68 Correct 2496 ms 362936 KB Output is correct
69 Correct 2515 ms 366920 KB Output is correct
70 Correct 3116 ms 356536 KB Output is correct
71 Correct 3224 ms 354700 KB Output is correct
72 Correct 2351 ms 389120 KB Output is correct
73 Correct 2491 ms 364792 KB Output is correct
74 Correct 2717 ms 359376 KB Output is correct
75 Correct 2865 ms 355864 KB Output is correct
76 Correct 1456 ms 353808 KB Output is correct
77 Correct 1428 ms 349532 KB Output is correct
78 Correct 1684 ms 350436 KB Output is correct
79 Correct 1729 ms 356260 KB Output is correct
80 Correct 1700 ms 352024 KB Output is correct
81 Correct 428 ms 105644 KB Output is correct
82 Correct 409 ms 104656 KB Output is correct
83 Correct 409 ms 101804 KB Output is correct
84 Correct 381 ms 99492 KB Output is correct
85 Correct 385 ms 101548 KB Output is correct
86 Correct 399 ms 97152 KB Output is correct
87 Correct 386 ms 98876 KB Output is correct
88 Correct 408 ms 100520 KB Output is correct
89 Correct 365 ms 97980 KB Output is correct
90 Correct 169 ms 94428 KB Output is correct
91 Correct 445 ms 106416 KB Output is correct
92 Correct 430 ms 102184 KB Output is correct
93 Correct 413 ms 101220 KB Output is correct
94 Correct 411 ms 97448 KB Output is correct
95 Correct 391 ms 96720 KB Output is correct
96 Correct 259 ms 84500 KB Output is correct
97 Correct 3092 ms 417184 KB Output is correct
98 Correct 1051 ms 316772 KB Output is correct
99 Correct 3582 ms 377228 KB Output is correct
100 Correct 2987 ms 408164 KB Output is correct
101 Correct 3015 ms 397596 KB Output is correct
102 Correct 3819 ms 385004 KB Output is correct
103 Correct 2398 ms 373444 KB Output is correct
104 Correct 2393 ms 372376 KB Output is correct
105 Correct 1827 ms 370040 KB Output is correct
106 Correct 1922 ms 371480 KB Output is correct
107 Correct 2693 ms 384692 KB Output is correct
108 Correct 2659 ms 388664 KB Output is correct
109 Correct 2669 ms 379372 KB Output is correct
110 Correct 2711 ms 389516 KB Output is correct
111 Correct 2801 ms 394024 KB Output is correct
112 Correct 2787 ms 376156 KB Output is correct
113 Correct 866 ms 360724 KB Output is correct
114 Correct 3063 ms 415392 KB Output is correct
115 Correct 3126 ms 398372 KB Output is correct
116 Correct 3136 ms 391440 KB Output is correct
117 Correct 3165 ms 379048 KB Output is correct
118 Correct 3005 ms 372676 KB Output is correct
119 Correct 1659 ms 317352 KB Output is correct
120 Correct 1193 ms 353148 KB Output is correct
121 Correct 1335 ms 365324 KB Output is correct
122 Correct 1335 ms 363072 KB Output is correct
123 Correct 1482 ms 366648 KB Output is correct
124 Correct 1610 ms 372580 KB Output is correct
125 Correct 1534 ms 368948 KB Output is correct
126 Correct 1601 ms 372168 KB Output is correct