#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int lim = 7e6;
struct Node{
int inc = -1e9, dec = -1e9;
Node *l = nullptr, *r = nullptr;
Node(){}
Node(Node *_l, Node *_r): l(_l), r(_r){}
void update(){
inc = -1e9;
if(l) inc = max(inc, l->inc);
if(r) inc = max(inc, r->inc);
dec = -1e9;
if(l) dec = max(dec, l->dec);
if(r) dec = max(dec, r->dec);
}
}Nodes[lim];
int ls_node = 0;
Node* newNode(){
return &Nodes[ls_node++];
}
struct sparse_segtree{
Node* root = newNode();
int n = 1;
sparse_segtree(int _n){
while(n < _n) n*=2;
}
void update(int i, Node *nd, int a, int b, int x, bool inc){
if(a == b){
if(inc) nd->inc = x+n-1-i;
else nd->dec = x+i;
return;
}
int m = (a+b)/2;
if(i <= m){
if(nd->l == nullptr) nd->l = newNode();
update(i, nd->l, a, m, x, inc);
}
else{
if(nd->r == nullptr) nd->r = newNode();
update(i, nd->r, m+1, b, x, inc);
}
nd->update();
}
void update(int i, int x, bool inc){
update(i, root, 0, n-1, x, inc);
}
int get(int l, int r, Node* nd, int a, int b, bool inc){
if(!nd) return -1e9;
if(a > r || b < l) return -1e9;
if(a >= l && b <= r){
if(inc) return nd->inc;
else return nd->dec;
}
int m = (a+b)/2;
return max(get(l, r, nd->l, a, m, inc), get(l, r, nd->r, m+1, b, inc));
}
int get(int l, int r, bool inc){
return get(l, r, root, 0, n-1, inc);
}
};
const int L = 1e8+5;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k, q; cin >> n >> k >> q;
vector<tuple<int, int, int, int>> queries;
for(int i = 0; i < n; i++){
int x, t, a, b; cin >> x >> t >> a >> b; t--;
queries.push_back({a, 0, x, t});
queries.push_back({b, 2, x, t});
}
for(int i = 0; i < q; i++){
int l, y; cin >> l >> y;
queries.push_back({y, 1, l, i});
}
sort(queries.begin(), queries.end());
vector<set<int>> stores(k);
vector<map<int, int>> cnt(k);
map<int, multiset<int>> mx[2];
sparse_segtree S(L);
auto add_to_mx = [&](int i, int x, bool inc){
if(mx[inc][i].empty() || x > *mx[inc][i].rbegin()) S.update(i, x, inc);
mx[inc][i].insert(x);
};
auto remove_from_mx = [&](int i, int x, bool inc){
mx[inc][i].erase(mx[inc][i].find(x));
if(mx[inc][i].empty()) S.update(i, -1e9, inc);
else if(x > *mx[inc][i].rbegin()) S.update(i, *mx[inc][i].rbegin(), inc);
};
auto add = [&](int t, int x){
cnt[t][x]++;
if(cnt[t][x] > 1) return;
auto it = stores[t].insert(x).first;
if(stores[t].size() == 1){
add_to_mx(0, x, false);
add_to_mx(L-1, L-1-x, true);
}
else if(it == stores[t].begin()){
remove_from_mx(0, *next(it), false);
add_to_mx(0, x, false);
int md = (x+*next(it))/2;
if(md > x) add_to_mx(md, md-x, true);
add_to_mx(md+1, *next(it)-md-1, false);
}
else if(next(it) == stores[t].end()){
remove_from_mx(L-1, L-1-*prev(it), true);
int md = (*prev(it)+x)/2;
if(md > *prev(it)) add_to_mx(md, md-*prev(it), true);
add_to_mx(md+1, x-md-1, false);
add_to_mx(L-1, L-1-x, true);
}
else{
int md = (*prev(it)+*next(it))/2;
if(md > *prev(it)) remove_from_mx(md, md-*prev(it), true);
remove_from_mx(md+1, *next(it)-md-1, false);
md = (*prev(it)+x)/2;
if(md > *prev(it)) add_to_mx(md, md-*prev(it), true);
add_to_mx(md+1, x-md-1, false);
md = (x+*next(it))/2;
if(md > x) add_to_mx(md, md-x, true);
add_to_mx(md+1, *next(it)-md-1, false);
}
};
auto remove = [&](int t, int x){
cnt[t][x]--;
if(cnt[t][x] > 0) return;
auto it = stores[t].find(x);
if(stores[t].size() == 1){
remove_from_mx(0, x, false);
remove_from_mx(L-1, L-1-x, true);
}
else if(it == stores[t].begin()){
add_to_mx(0, *next(it), false);
remove_from_mx(0, x, false);
int md = (x+*next(it))/2;
if(md > x) remove_from_mx(md, md-x, true);
remove_from_mx(md+1, *next(it)-md-1, false);
}
else if(next(it) == stores[t].end()){
add_to_mx(L-1, L-1-*prev(it), true);
int md = (*prev(it)+x)/2;
if(md > *prev(it)) remove_from_mx(md, md-*prev(it), true);
remove_from_mx(md+1, x-md-1, false);
remove_from_mx(L-1, L-1-x, true);
}
else{
int md = (*prev(it)+*next(it))/2;
if(md > *prev(it)) add_to_mx(md, md-*prev(it), true);
add_to_mx(md+1, *next(it)-md-1, false);
md = (*prev(it)+x)/2;
if(md > *prev(it)) remove_from_mx(md, md-*prev(it), true);
remove_from_mx(md+1, x-md-1, false);
md = (x+*next(it))/2;
if(md > x) remove_from_mx(md, md-x, true);
remove_from_mx(md+1, *next(it)-md-1, false);
}
stores[t].erase(it);
};
vector<int> cnt_t(k, 0);
int nonzero = 0;
vector<int> ans(q);
for(auto [_, type, x, i]: queries){
if(type == 0){
cnt_t[i]++;
if(cnt_t[i] == 1) nonzero++;
add(i, x);
}
else if(type == 2){
cnt_t[i]--;
if(cnt_t[i] == 0) nonzero--;
remove(i, x);
}
else{
if(nonzero < k) ans[i] = -1;
else ans[i] = max(S.get(0, x, 0)-x, S.get(x, S.n-1, 1)-(S.n-1)+x);
}
}
for(int x: ans) cout << x << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
164692 KB |
Output is correct |
2 |
Correct |
30 ms |
164772 KB |
Output is correct |
3 |
Correct |
29 ms |
164620 KB |
Output is correct |
4 |
Correct |
26 ms |
164700 KB |
Output is correct |
5 |
Correct |
27 ms |
164856 KB |
Output is correct |
6 |
Correct |
29 ms |
164956 KB |
Output is correct |
7 |
Correct |
27 ms |
164720 KB |
Output is correct |
8 |
Correct |
28 ms |
164956 KB |
Output is correct |
9 |
Correct |
28 ms |
164976 KB |
Output is correct |
10 |
Correct |
29 ms |
164956 KB |
Output is correct |
11 |
Correct |
31 ms |
164900 KB |
Output is correct |
12 |
Correct |
29 ms |
164956 KB |
Output is correct |
13 |
Correct |
29 ms |
164948 KB |
Output is correct |
14 |
Correct |
27 ms |
164692 KB |
Output is correct |
15 |
Correct |
28 ms |
164944 KB |
Output is correct |
16 |
Correct |
28 ms |
164948 KB |
Output is correct |
17 |
Correct |
27 ms |
164952 KB |
Output is correct |
18 |
Correct |
28 ms |
165168 KB |
Output is correct |
19 |
Correct |
29 ms |
164952 KB |
Output is correct |
20 |
Correct |
28 ms |
164956 KB |
Output is correct |
21 |
Correct |
29 ms |
164892 KB |
Output is correct |
22 |
Correct |
27 ms |
164952 KB |
Output is correct |
23 |
Correct |
28 ms |
164948 KB |
Output is correct |
24 |
Correct |
29 ms |
164944 KB |
Output is correct |
25 |
Correct |
30 ms |
164776 KB |
Output is correct |
26 |
Correct |
29 ms |
164900 KB |
Output is correct |
27 |
Correct |
28 ms |
164716 KB |
Output is correct |
28 |
Correct |
29 ms |
164684 KB |
Output is correct |
29 |
Correct |
28 ms |
164956 KB |
Output is correct |
30 |
Correct |
28 ms |
164864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
164692 KB |
Output is correct |
2 |
Correct |
30 ms |
164772 KB |
Output is correct |
3 |
Correct |
29 ms |
164620 KB |
Output is correct |
4 |
Correct |
26 ms |
164700 KB |
Output is correct |
5 |
Correct |
27 ms |
164856 KB |
Output is correct |
6 |
Correct |
29 ms |
164956 KB |
Output is correct |
7 |
Correct |
27 ms |
164720 KB |
Output is correct |
8 |
Correct |
28 ms |
164956 KB |
Output is correct |
9 |
Correct |
28 ms |
164976 KB |
Output is correct |
10 |
Correct |
29 ms |
164956 KB |
Output is correct |
11 |
Correct |
31 ms |
164900 KB |
Output is correct |
12 |
Correct |
29 ms |
164956 KB |
Output is correct |
13 |
Correct |
29 ms |
164948 KB |
Output is correct |
14 |
Correct |
27 ms |
164692 KB |
Output is correct |
15 |
Correct |
28 ms |
164944 KB |
Output is correct |
16 |
Correct |
28 ms |
164948 KB |
Output is correct |
17 |
Correct |
27 ms |
164952 KB |
Output is correct |
18 |
Correct |
28 ms |
165168 KB |
Output is correct |
19 |
Correct |
29 ms |
164952 KB |
Output is correct |
20 |
Correct |
28 ms |
164956 KB |
Output is correct |
21 |
Correct |
29 ms |
164892 KB |
Output is correct |
22 |
Correct |
27 ms |
164952 KB |
Output is correct |
23 |
Correct |
28 ms |
164948 KB |
Output is correct |
24 |
Correct |
29 ms |
164944 KB |
Output is correct |
25 |
Correct |
30 ms |
164776 KB |
Output is correct |
26 |
Correct |
29 ms |
164900 KB |
Output is correct |
27 |
Correct |
28 ms |
164716 KB |
Output is correct |
28 |
Correct |
29 ms |
164684 KB |
Output is correct |
29 |
Correct |
28 ms |
164956 KB |
Output is correct |
30 |
Correct |
28 ms |
164864 KB |
Output is correct |
31 |
Correct |
1072 ms |
211048 KB |
Output is correct |
32 |
Correct |
78 ms |
170668 KB |
Output is correct |
33 |
Correct |
1022 ms |
205504 KB |
Output is correct |
34 |
Correct |
1085 ms |
203596 KB |
Output is correct |
35 |
Correct |
1107 ms |
210996 KB |
Output is correct |
36 |
Correct |
1052 ms |
212112 KB |
Output is correct |
37 |
Correct |
673 ms |
202400 KB |
Output is correct |
38 |
Correct |
662 ms |
203612 KB |
Output is correct |
39 |
Correct |
543 ms |
201920 KB |
Output is correct |
40 |
Correct |
557 ms |
202320 KB |
Output is correct |
41 |
Correct |
437 ms |
186616 KB |
Output is correct |
42 |
Correct |
478 ms |
185948 KB |
Output is correct |
43 |
Correct |
76 ms |
169420 KB |
Output is correct |
44 |
Correct |
443 ms |
187372 KB |
Output is correct |
45 |
Correct |
438 ms |
186560 KB |
Output is correct |
46 |
Correct |
419 ms |
186048 KB |
Output is correct |
47 |
Correct |
266 ms |
181952 KB |
Output is correct |
48 |
Correct |
267 ms |
184124 KB |
Output is correct |
49 |
Correct |
297 ms |
184892 KB |
Output is correct |
50 |
Correct |
304 ms |
184780 KB |
Output is correct |
51 |
Correct |
332 ms |
185064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2686 ms |
290832 KB |
Output is correct |
2 |
Correct |
1516 ms |
294568 KB |
Output is correct |
3 |
Correct |
729 ms |
268484 KB |
Output is correct |
4 |
Correct |
2420 ms |
287224 KB |
Output is correct |
5 |
Correct |
1550 ms |
294408 KB |
Output is correct |
6 |
Correct |
1512 ms |
295580 KB |
Output is correct |
7 |
Correct |
680 ms |
268960 KB |
Output is correct |
8 |
Correct |
2482 ms |
288040 KB |
Output is correct |
9 |
Correct |
2781 ms |
294120 KB |
Output is correct |
10 |
Correct |
1953 ms |
294940 KB |
Output is correct |
11 |
Correct |
1440 ms |
292964 KB |
Output is correct |
12 |
Correct |
1579 ms |
294744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5009 ms |
318676 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
164692 KB |
Output is correct |
2 |
Correct |
30 ms |
164772 KB |
Output is correct |
3 |
Correct |
29 ms |
164620 KB |
Output is correct |
4 |
Correct |
26 ms |
164700 KB |
Output is correct |
5 |
Correct |
27 ms |
164856 KB |
Output is correct |
6 |
Correct |
29 ms |
164956 KB |
Output is correct |
7 |
Correct |
27 ms |
164720 KB |
Output is correct |
8 |
Correct |
28 ms |
164956 KB |
Output is correct |
9 |
Correct |
28 ms |
164976 KB |
Output is correct |
10 |
Correct |
29 ms |
164956 KB |
Output is correct |
11 |
Correct |
31 ms |
164900 KB |
Output is correct |
12 |
Correct |
29 ms |
164956 KB |
Output is correct |
13 |
Correct |
29 ms |
164948 KB |
Output is correct |
14 |
Correct |
27 ms |
164692 KB |
Output is correct |
15 |
Correct |
28 ms |
164944 KB |
Output is correct |
16 |
Correct |
28 ms |
164948 KB |
Output is correct |
17 |
Correct |
27 ms |
164952 KB |
Output is correct |
18 |
Correct |
28 ms |
165168 KB |
Output is correct |
19 |
Correct |
29 ms |
164952 KB |
Output is correct |
20 |
Correct |
28 ms |
164956 KB |
Output is correct |
21 |
Correct |
29 ms |
164892 KB |
Output is correct |
22 |
Correct |
27 ms |
164952 KB |
Output is correct |
23 |
Correct |
28 ms |
164948 KB |
Output is correct |
24 |
Correct |
29 ms |
164944 KB |
Output is correct |
25 |
Correct |
30 ms |
164776 KB |
Output is correct |
26 |
Correct |
29 ms |
164900 KB |
Output is correct |
27 |
Correct |
28 ms |
164716 KB |
Output is correct |
28 |
Correct |
29 ms |
164684 KB |
Output is correct |
29 |
Correct |
28 ms |
164956 KB |
Output is correct |
30 |
Correct |
28 ms |
164864 KB |
Output is correct |
31 |
Correct |
1072 ms |
211048 KB |
Output is correct |
32 |
Correct |
78 ms |
170668 KB |
Output is correct |
33 |
Correct |
1022 ms |
205504 KB |
Output is correct |
34 |
Correct |
1085 ms |
203596 KB |
Output is correct |
35 |
Correct |
1107 ms |
210996 KB |
Output is correct |
36 |
Correct |
1052 ms |
212112 KB |
Output is correct |
37 |
Correct |
673 ms |
202400 KB |
Output is correct |
38 |
Correct |
662 ms |
203612 KB |
Output is correct |
39 |
Correct |
543 ms |
201920 KB |
Output is correct |
40 |
Correct |
557 ms |
202320 KB |
Output is correct |
41 |
Correct |
437 ms |
186616 KB |
Output is correct |
42 |
Correct |
478 ms |
185948 KB |
Output is correct |
43 |
Correct |
76 ms |
169420 KB |
Output is correct |
44 |
Correct |
443 ms |
187372 KB |
Output is correct |
45 |
Correct |
438 ms |
186560 KB |
Output is correct |
46 |
Correct |
419 ms |
186048 KB |
Output is correct |
47 |
Correct |
266 ms |
181952 KB |
Output is correct |
48 |
Correct |
267 ms |
184124 KB |
Output is correct |
49 |
Correct |
297 ms |
184892 KB |
Output is correct |
50 |
Correct |
304 ms |
184780 KB |
Output is correct |
51 |
Correct |
332 ms |
185064 KB |
Output is correct |
52 |
Correct |
142 ms |
186376 KB |
Output is correct |
53 |
Correct |
146 ms |
179048 KB |
Output is correct |
54 |
Correct |
483 ms |
191124 KB |
Output is correct |
55 |
Correct |
359 ms |
186520 KB |
Output is correct |
56 |
Correct |
297 ms |
186232 KB |
Output is correct |
57 |
Correct |
432 ms |
186208 KB |
Output is correct |
58 |
Correct |
337 ms |
185120 KB |
Output is correct |
59 |
Correct |
306 ms |
183968 KB |
Output is correct |
60 |
Correct |
410 ms |
186508 KB |
Output is correct |
61 |
Correct |
115 ms |
186596 KB |
Output is correct |
62 |
Correct |
155 ms |
185428 KB |
Output is correct |
63 |
Correct |
344 ms |
186956 KB |
Output is correct |
64 |
Correct |
411 ms |
187888 KB |
Output is correct |
65 |
Correct |
481 ms |
187124 KB |
Output is correct |
66 |
Correct |
451 ms |
186044 KB |
Output is correct |
67 |
Correct |
187 ms |
173000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
164692 KB |
Output is correct |
2 |
Correct |
30 ms |
164772 KB |
Output is correct |
3 |
Correct |
29 ms |
164620 KB |
Output is correct |
4 |
Correct |
26 ms |
164700 KB |
Output is correct |
5 |
Correct |
27 ms |
164856 KB |
Output is correct |
6 |
Correct |
29 ms |
164956 KB |
Output is correct |
7 |
Correct |
27 ms |
164720 KB |
Output is correct |
8 |
Correct |
28 ms |
164956 KB |
Output is correct |
9 |
Correct |
28 ms |
164976 KB |
Output is correct |
10 |
Correct |
29 ms |
164956 KB |
Output is correct |
11 |
Correct |
31 ms |
164900 KB |
Output is correct |
12 |
Correct |
29 ms |
164956 KB |
Output is correct |
13 |
Correct |
29 ms |
164948 KB |
Output is correct |
14 |
Correct |
27 ms |
164692 KB |
Output is correct |
15 |
Correct |
28 ms |
164944 KB |
Output is correct |
16 |
Correct |
28 ms |
164948 KB |
Output is correct |
17 |
Correct |
27 ms |
164952 KB |
Output is correct |
18 |
Correct |
28 ms |
165168 KB |
Output is correct |
19 |
Correct |
29 ms |
164952 KB |
Output is correct |
20 |
Correct |
28 ms |
164956 KB |
Output is correct |
21 |
Correct |
29 ms |
164892 KB |
Output is correct |
22 |
Correct |
27 ms |
164952 KB |
Output is correct |
23 |
Correct |
28 ms |
164948 KB |
Output is correct |
24 |
Correct |
29 ms |
164944 KB |
Output is correct |
25 |
Correct |
30 ms |
164776 KB |
Output is correct |
26 |
Correct |
29 ms |
164900 KB |
Output is correct |
27 |
Correct |
28 ms |
164716 KB |
Output is correct |
28 |
Correct |
29 ms |
164684 KB |
Output is correct |
29 |
Correct |
28 ms |
164956 KB |
Output is correct |
30 |
Correct |
28 ms |
164864 KB |
Output is correct |
31 |
Correct |
1072 ms |
211048 KB |
Output is correct |
32 |
Correct |
78 ms |
170668 KB |
Output is correct |
33 |
Correct |
1022 ms |
205504 KB |
Output is correct |
34 |
Correct |
1085 ms |
203596 KB |
Output is correct |
35 |
Correct |
1107 ms |
210996 KB |
Output is correct |
36 |
Correct |
1052 ms |
212112 KB |
Output is correct |
37 |
Correct |
673 ms |
202400 KB |
Output is correct |
38 |
Correct |
662 ms |
203612 KB |
Output is correct |
39 |
Correct |
543 ms |
201920 KB |
Output is correct |
40 |
Correct |
557 ms |
202320 KB |
Output is correct |
41 |
Correct |
437 ms |
186616 KB |
Output is correct |
42 |
Correct |
478 ms |
185948 KB |
Output is correct |
43 |
Correct |
76 ms |
169420 KB |
Output is correct |
44 |
Correct |
443 ms |
187372 KB |
Output is correct |
45 |
Correct |
438 ms |
186560 KB |
Output is correct |
46 |
Correct |
419 ms |
186048 KB |
Output is correct |
47 |
Correct |
266 ms |
181952 KB |
Output is correct |
48 |
Correct |
267 ms |
184124 KB |
Output is correct |
49 |
Correct |
297 ms |
184892 KB |
Output is correct |
50 |
Correct |
304 ms |
184780 KB |
Output is correct |
51 |
Correct |
332 ms |
185064 KB |
Output is correct |
52 |
Correct |
2686 ms |
290832 KB |
Output is correct |
53 |
Correct |
1516 ms |
294568 KB |
Output is correct |
54 |
Correct |
729 ms |
268484 KB |
Output is correct |
55 |
Correct |
2420 ms |
287224 KB |
Output is correct |
56 |
Correct |
1550 ms |
294408 KB |
Output is correct |
57 |
Correct |
1512 ms |
295580 KB |
Output is correct |
58 |
Correct |
680 ms |
268960 KB |
Output is correct |
59 |
Correct |
2482 ms |
288040 KB |
Output is correct |
60 |
Correct |
2781 ms |
294120 KB |
Output is correct |
61 |
Correct |
1953 ms |
294940 KB |
Output is correct |
62 |
Correct |
1440 ms |
292964 KB |
Output is correct |
63 |
Correct |
1579 ms |
294744 KB |
Output is correct |
64 |
Execution timed out |
5009 ms |
318676 KB |
Time limit exceeded |
65 |
Halted |
0 ms |
0 KB |
- |