#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
#define int ll
using ld = long double;
using pii = pair<int, int>;
#define F first
#define S second
const ld PI = 3.1415926535;
const int N = 5e5 + 2;
const int M = 2e6 + 1;
int mod = 998244353;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
int mult(int a, int b) {
return a * 1LL * b % mod;
}
int sum(int a, int b) {
if (a + b < 0)
return a + b + mod;
if (a + b >= mod)
return a + b - mod;
return a + b;
}
ll binpow(ll a, ll n) {
if (n == 0)
return 1;
if (n % 2 == 1) {
return binpow(a, n - 1) * a % mod;
} else {
ll b = binpow(a, n / 2);
return b * b % mod;
}
}
struct segtree{
vector<int> t, l, r;
segtree(){
t.assign(1, -infi);
l.assign(1, -1);
r.assign(1, -1);
}
void zer(int v, int tl, int tr, int i){
if(tl == tr){
t[v] = -infi;
//cout << v << ' ' << l[v] << ' ' << r[v] << ' ' << tl << ' ' << tr << ' ' << t[v] << '\n';
return;
}
int tm = (tl + tr) / 2;
if(i <= tm){
if(l[v] == -1){
l[v] = t.size();
t.push_back(-infi);
l.push_back(-1);
r.push_back(-1);
}
zer(l[v], tl, tm, i);
}else{
if(r[v] == -1){
r[v] = t.size();
t.push_back(-infi);
l.push_back(-1);
r.push_back(-1);
}
zer(r[v], tm + 1, tr, i);
}
t[v] = -infi;
if(l[v] != -1)
t[v] = max(t[v], t[l[v]]);
if(r[v] != -1)
t[v] = max(t[v], t[r[v]]);
}
void add(int v, int tl, int tr, int i, int x){
if(tl == tr){
t[v] = max(t[v], x);
//cout << v << ' ' << l[v] << ' ' << r[v] << ' ' << tl << ' ' << tr << ' ' << t[v] << '\n';
return;
}
int tm = (tl + tr) / 2;
if(i <= tm){
if(l[v] == -1){
l[v] = t.size();
t.push_back(-infi);
l.push_back(-1);
r.push_back(-1);
}
add(l[v], tl, tm, i, x);
}else{
if(r[v] == -1){
r[v] = t.size();
t.push_back(-infi);
l.push_back(-1);
r.push_back(-1);
}
add(r[v], tm + 1, tr, i, x);
}
t[v] = -infi;
if(l[v] != -1)
t[v] = max(t[v], t[l[v]]);
if(r[v] != -1)
t[v] = max(t[v], t[r[v]]);
//cout << v << ' ' << l[v] << ' ' << r[v] << ' ' << tl << ' ' << tr << ' ' << t[v] << '\n';
}
int get(int v, int tl, int tr, int lu, int ru){
if(v == -1)
return -infi;
if(tl > ru || lu > tr)
return -infi;
if(lu <= tl && tr <= ru)
return t[v];
int tm = (tl + tr) / 2;
return max(get(l[v], tl, tm, lu, ru), get(r[v], tm + 1, tr, lu, ru));
}
};
int n, q, k, ans[N], L = 0, R = 2e8;
vector<pair<pii, pii>> evs;
multiset<int> cr[N];
map<int, multiset<int>> spl, spr;
segtree lt = segtree(), rt = segtree();
void add(int i, int x1, int x2){
lt.add(0, L, R, i, x1);
rt.add(0, L, R, i, x2);
spl[i].insert(x1);
spr[i].insert(x2);
}
void rem(int i, int x1, int x2){
lt.zer(0, L, R, i);
rt.zer(0, L, R, i);
spl[i].erase(spl[i].find(x1));
spr[i].erase(spr[i].find(x2));
if(spl[i].size() > 0)
lt.add(0, L, R, i, *(--spl[i].end()));
if(spr[i].size() > 0)
rt.add(0, L, R, i, *(--spr[i].end()));
}
void solve() {
cin >> n >> k >> q;
for(int i = 1; i <= n; i++){
int x, tp, a, b;
cin >> x >> tp >> a >> b;
x *= 2;
evs.push_back({{a, 1}, {x, tp}});
evs.push_back({{b + 1, -1}, {x, tp}});
}
for(int i = 1; i <= q; i++){
int l, y;
cin >> l >> y;
l *= 2;
evs.push_back({{y, 2}, {l, i}});
}
sort(evs.begin(), evs.end());
int cnt = k;
for(auto ev : evs){
//cout << ev.F.F << ' ' << ev.F.S << ' ' << ev.S.F << ' ' << ev.S.S << '\n';
if(ev.F.S == 1){
int x = ev.S.F, tp = ev.S.S;
if(cr[tp].find(x) != cr[tp].end()){
cr[tp].insert(x);
continue;
}
if(cr[tp].size() == 0){
cr[tp].insert(x);
add(L, x, x - 2 * L);
add(R, 2 * R - x, -x);
cnt--;
continue;
}
int l = -1, r = -1;
auto it = cr[tp].upper_bound(x);
if(it != cr[tp].end()){
add(((*it) + x) / 2, *it, -x);
r = *it;
}else{
add(R, 2 * R - x, -x);
}
it = cr[tp].lower_bound(x);
if(it != cr[tp].begin()){
it--;
add((x + (*it)) / 2, x, -(*it));
l = *it;
}else{
add(L, x, x - 2 * L);
}
if(l != -1 && r != -1){
rem((r + l) / 2, r, -l);
}
if(r == -1 && l != -1){
rem(R, 2 * R - l, -l);
}
if(r != -1 && l == -1){
rem(L, r, r - 2 * L);
}
cr[tp].insert(x);
}else if(ev.F.S == -1){
int x = ev.S.F, tp = ev.S.S;
int l = -1, r = -1;
if(cr[tp].count(x) > 1){
cr[tp].erase(cr[tp].find(x));
continue;
}
auto it = cr[tp].upper_bound(x);
if(it != cr[tp].end()){
r = *it;
rem((r + x) / 2, r, -x);
}else{
rem(R, 2 * R - x, -x);
}
it = cr[tp].lower_bound(x);
if(it != cr[tp].begin()){
it--;
l = (*it);
rem((x + l) / 2, x, -l);
}else{
rem(L, x, x - 2 * L);
}
cr[tp].erase(cr[tp].find(x));
if(l == -1 && r == -1){
cnt++;
assert(cr[tp].size() == 0);
}else if(l == -1){
add(L, r, r - 2 * L);
}else if(r == -1){
add(R, 2 * R - l, -l);
}else{
add((r + l) / 2, r, -l);
}
}else{
int x = ev.S.F, i = ev.S.S;
int ret = max(lt.get(0, L, R, L, x) - x, rt.get(0, L, R, x, R) + x);
if(cnt != 0)
ans[i] = -1;
else
ans[i] = (ret < 0 ? -1 : ret / 2);
}
//cout << cnt << '\n';
}
for(int i = 1; i <=q; i++)
cout << ans[i] << ' ';
cout << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
25168 KB |
Output is correct |
2 |
Correct |
5 ms |
25168 KB |
Output is correct |
3 |
Correct |
4 ms |
25168 KB |
Output is correct |
4 |
Correct |
4 ms |
25168 KB |
Output is correct |
5 |
Correct |
6 ms |
25168 KB |
Output is correct |
6 |
Correct |
11 ms |
26564 KB |
Output is correct |
7 |
Correct |
6 ms |
25168 KB |
Output is correct |
8 |
Correct |
8 ms |
25716 KB |
Output is correct |
9 |
Correct |
6 ms |
25168 KB |
Output is correct |
10 |
Correct |
8 ms |
26564 KB |
Output is correct |
11 |
Correct |
7 ms |
25848 KB |
Output is correct |
12 |
Correct |
12 ms |
26192 KB |
Output is correct |
13 |
Correct |
7 ms |
25424 KB |
Output is correct |
14 |
Correct |
15 ms |
25692 KB |
Output is correct |
15 |
Correct |
14 ms |
25700 KB |
Output is correct |
16 |
Correct |
14 ms |
25576 KB |
Output is correct |
17 |
Correct |
18 ms |
25936 KB |
Output is correct |
18 |
Correct |
21 ms |
24400 KB |
Output is correct |
19 |
Correct |
19 ms |
24400 KB |
Output is correct |
20 |
Correct |
18 ms |
24672 KB |
Output is correct |
21 |
Correct |
14 ms |
25180 KB |
Output is correct |
22 |
Correct |
16 ms |
25424 KB |
Output is correct |
23 |
Correct |
17 ms |
24400 KB |
Output is correct |
24 |
Correct |
16 ms |
24412 KB |
Output is correct |
25 |
Correct |
19 ms |
24656 KB |
Output is correct |
26 |
Correct |
17 ms |
25952 KB |
Output is correct |
27 |
Correct |
17 ms |
25168 KB |
Output is correct |
28 |
Correct |
14 ms |
25680 KB |
Output is correct |
29 |
Correct |
11 ms |
25680 KB |
Output is correct |
30 |
Correct |
12 ms |
25424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
25168 KB |
Output is correct |
2 |
Correct |
5 ms |
25168 KB |
Output is correct |
3 |
Correct |
4 ms |
25168 KB |
Output is correct |
4 |
Correct |
4 ms |
25168 KB |
Output is correct |
5 |
Correct |
6 ms |
25168 KB |
Output is correct |
6 |
Correct |
11 ms |
26564 KB |
Output is correct |
7 |
Correct |
6 ms |
25168 KB |
Output is correct |
8 |
Correct |
8 ms |
25716 KB |
Output is correct |
9 |
Correct |
6 ms |
25168 KB |
Output is correct |
10 |
Correct |
8 ms |
26564 KB |
Output is correct |
11 |
Correct |
7 ms |
25848 KB |
Output is correct |
12 |
Correct |
12 ms |
26192 KB |
Output is correct |
13 |
Correct |
7 ms |
25424 KB |
Output is correct |
14 |
Correct |
15 ms |
25692 KB |
Output is correct |
15 |
Correct |
14 ms |
25700 KB |
Output is correct |
16 |
Correct |
14 ms |
25576 KB |
Output is correct |
17 |
Correct |
18 ms |
25936 KB |
Output is correct |
18 |
Correct |
21 ms |
24400 KB |
Output is correct |
19 |
Correct |
19 ms |
24400 KB |
Output is correct |
20 |
Correct |
18 ms |
24672 KB |
Output is correct |
21 |
Correct |
14 ms |
25180 KB |
Output is correct |
22 |
Correct |
16 ms |
25424 KB |
Output is correct |
23 |
Correct |
17 ms |
24400 KB |
Output is correct |
24 |
Correct |
16 ms |
24412 KB |
Output is correct |
25 |
Correct |
19 ms |
24656 KB |
Output is correct |
26 |
Correct |
17 ms |
25952 KB |
Output is correct |
27 |
Correct |
17 ms |
25168 KB |
Output is correct |
28 |
Correct |
14 ms |
25680 KB |
Output is correct |
29 |
Correct |
11 ms |
25680 KB |
Output is correct |
30 |
Correct |
12 ms |
25424 KB |
Output is correct |
31 |
Correct |
1490 ms |
159016 KB |
Output is correct |
32 |
Correct |
125 ms |
34244 KB |
Output is correct |
33 |
Correct |
1379 ms |
156676 KB |
Output is correct |
34 |
Correct |
1403 ms |
153328 KB |
Output is correct |
35 |
Correct |
1518 ms |
166644 KB |
Output is correct |
36 |
Correct |
1468 ms |
173160 KB |
Output is correct |
37 |
Correct |
941 ms |
157296 KB |
Output is correct |
38 |
Correct |
939 ms |
154976 KB |
Output is correct |
39 |
Correct |
616 ms |
153176 KB |
Output is correct |
40 |
Correct |
603 ms |
155288 KB |
Output is correct |
41 |
Correct |
660 ms |
94760 KB |
Output is correct |
42 |
Correct |
706 ms |
96284 KB |
Output is correct |
43 |
Correct |
83 ms |
35748 KB |
Output is correct |
44 |
Correct |
723 ms |
95964 KB |
Output is correct |
45 |
Correct |
709 ms |
96020 KB |
Output is correct |
46 |
Correct |
647 ms |
94228 KB |
Output is correct |
47 |
Correct |
363 ms |
90288 KB |
Output is correct |
48 |
Correct |
362 ms |
98892 KB |
Output is correct |
49 |
Correct |
420 ms |
98856 KB |
Output is correct |
50 |
Correct |
476 ms |
99312 KB |
Output is correct |
51 |
Correct |
466 ms |
99096 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4070 ms |
316788 KB |
Output is correct |
2 |
Correct |
2665 ms |
328264 KB |
Output is correct |
3 |
Correct |
1176 ms |
129184 KB |
Output is correct |
4 |
Correct |
3687 ms |
312048 KB |
Output is correct |
5 |
Correct |
2047 ms |
323612 KB |
Output is correct |
6 |
Correct |
2405 ms |
325252 KB |
Output is correct |
7 |
Correct |
1162 ms |
130460 KB |
Output is correct |
8 |
Correct |
3757 ms |
310968 KB |
Output is correct |
9 |
Correct |
3494 ms |
319664 KB |
Output is correct |
10 |
Correct |
2623 ms |
320588 KB |
Output is correct |
11 |
Correct |
2234 ms |
318500 KB |
Output is correct |
12 |
Correct |
2317 ms |
319432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
5084 ms |
463148 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
25168 KB |
Output is correct |
2 |
Correct |
5 ms |
25168 KB |
Output is correct |
3 |
Correct |
4 ms |
25168 KB |
Output is correct |
4 |
Correct |
4 ms |
25168 KB |
Output is correct |
5 |
Correct |
6 ms |
25168 KB |
Output is correct |
6 |
Correct |
11 ms |
26564 KB |
Output is correct |
7 |
Correct |
6 ms |
25168 KB |
Output is correct |
8 |
Correct |
8 ms |
25716 KB |
Output is correct |
9 |
Correct |
6 ms |
25168 KB |
Output is correct |
10 |
Correct |
8 ms |
26564 KB |
Output is correct |
11 |
Correct |
7 ms |
25848 KB |
Output is correct |
12 |
Correct |
12 ms |
26192 KB |
Output is correct |
13 |
Correct |
7 ms |
25424 KB |
Output is correct |
14 |
Correct |
15 ms |
25692 KB |
Output is correct |
15 |
Correct |
14 ms |
25700 KB |
Output is correct |
16 |
Correct |
14 ms |
25576 KB |
Output is correct |
17 |
Correct |
18 ms |
25936 KB |
Output is correct |
18 |
Correct |
21 ms |
24400 KB |
Output is correct |
19 |
Correct |
19 ms |
24400 KB |
Output is correct |
20 |
Correct |
18 ms |
24672 KB |
Output is correct |
21 |
Correct |
14 ms |
25180 KB |
Output is correct |
22 |
Correct |
16 ms |
25424 KB |
Output is correct |
23 |
Correct |
17 ms |
24400 KB |
Output is correct |
24 |
Correct |
16 ms |
24412 KB |
Output is correct |
25 |
Correct |
19 ms |
24656 KB |
Output is correct |
26 |
Correct |
17 ms |
25952 KB |
Output is correct |
27 |
Correct |
17 ms |
25168 KB |
Output is correct |
28 |
Correct |
14 ms |
25680 KB |
Output is correct |
29 |
Correct |
11 ms |
25680 KB |
Output is correct |
30 |
Correct |
12 ms |
25424 KB |
Output is correct |
31 |
Correct |
1490 ms |
159016 KB |
Output is correct |
32 |
Correct |
125 ms |
34244 KB |
Output is correct |
33 |
Correct |
1379 ms |
156676 KB |
Output is correct |
34 |
Correct |
1403 ms |
153328 KB |
Output is correct |
35 |
Correct |
1518 ms |
166644 KB |
Output is correct |
36 |
Correct |
1468 ms |
173160 KB |
Output is correct |
37 |
Correct |
941 ms |
157296 KB |
Output is correct |
38 |
Correct |
939 ms |
154976 KB |
Output is correct |
39 |
Correct |
616 ms |
153176 KB |
Output is correct |
40 |
Correct |
603 ms |
155288 KB |
Output is correct |
41 |
Correct |
660 ms |
94760 KB |
Output is correct |
42 |
Correct |
706 ms |
96284 KB |
Output is correct |
43 |
Correct |
83 ms |
35748 KB |
Output is correct |
44 |
Correct |
723 ms |
95964 KB |
Output is correct |
45 |
Correct |
709 ms |
96020 KB |
Output is correct |
46 |
Correct |
647 ms |
94228 KB |
Output is correct |
47 |
Correct |
363 ms |
90288 KB |
Output is correct |
48 |
Correct |
362 ms |
98892 KB |
Output is correct |
49 |
Correct |
420 ms |
98856 KB |
Output is correct |
50 |
Correct |
476 ms |
99312 KB |
Output is correct |
51 |
Correct |
466 ms |
99096 KB |
Output is correct |
52 |
Correct |
252 ms |
45604 KB |
Output is correct |
53 |
Correct |
252 ms |
36632 KB |
Output is correct |
54 |
Correct |
724 ms |
97076 KB |
Output is correct |
55 |
Correct |
512 ms |
93476 KB |
Output is correct |
56 |
Correct |
430 ms |
96536 KB |
Output is correct |
57 |
Correct |
582 ms |
99184 KB |
Output is correct |
58 |
Correct |
549 ms |
92852 KB |
Output is correct |
59 |
Correct |
500 ms |
95404 KB |
Output is correct |
60 |
Correct |
693 ms |
98308 KB |
Output is correct |
61 |
Correct |
207 ms |
46000 KB |
Output is correct |
62 |
Correct |
251 ms |
45744 KB |
Output is correct |
63 |
Correct |
607 ms |
70684 KB |
Output is correct |
64 |
Correct |
665 ms |
95784 KB |
Output is correct |
65 |
Correct |
898 ms |
99372 KB |
Output is correct |
66 |
Correct |
671 ms |
97828 KB |
Output is correct |
67 |
Correct |
335 ms |
35524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
25168 KB |
Output is correct |
2 |
Correct |
5 ms |
25168 KB |
Output is correct |
3 |
Correct |
4 ms |
25168 KB |
Output is correct |
4 |
Correct |
4 ms |
25168 KB |
Output is correct |
5 |
Correct |
6 ms |
25168 KB |
Output is correct |
6 |
Correct |
11 ms |
26564 KB |
Output is correct |
7 |
Correct |
6 ms |
25168 KB |
Output is correct |
8 |
Correct |
8 ms |
25716 KB |
Output is correct |
9 |
Correct |
6 ms |
25168 KB |
Output is correct |
10 |
Correct |
8 ms |
26564 KB |
Output is correct |
11 |
Correct |
7 ms |
25848 KB |
Output is correct |
12 |
Correct |
12 ms |
26192 KB |
Output is correct |
13 |
Correct |
7 ms |
25424 KB |
Output is correct |
14 |
Correct |
15 ms |
25692 KB |
Output is correct |
15 |
Correct |
14 ms |
25700 KB |
Output is correct |
16 |
Correct |
14 ms |
25576 KB |
Output is correct |
17 |
Correct |
18 ms |
25936 KB |
Output is correct |
18 |
Correct |
21 ms |
24400 KB |
Output is correct |
19 |
Correct |
19 ms |
24400 KB |
Output is correct |
20 |
Correct |
18 ms |
24672 KB |
Output is correct |
21 |
Correct |
14 ms |
25180 KB |
Output is correct |
22 |
Correct |
16 ms |
25424 KB |
Output is correct |
23 |
Correct |
17 ms |
24400 KB |
Output is correct |
24 |
Correct |
16 ms |
24412 KB |
Output is correct |
25 |
Correct |
19 ms |
24656 KB |
Output is correct |
26 |
Correct |
17 ms |
25952 KB |
Output is correct |
27 |
Correct |
17 ms |
25168 KB |
Output is correct |
28 |
Correct |
14 ms |
25680 KB |
Output is correct |
29 |
Correct |
11 ms |
25680 KB |
Output is correct |
30 |
Correct |
12 ms |
25424 KB |
Output is correct |
31 |
Correct |
1490 ms |
159016 KB |
Output is correct |
32 |
Correct |
125 ms |
34244 KB |
Output is correct |
33 |
Correct |
1379 ms |
156676 KB |
Output is correct |
34 |
Correct |
1403 ms |
153328 KB |
Output is correct |
35 |
Correct |
1518 ms |
166644 KB |
Output is correct |
36 |
Correct |
1468 ms |
173160 KB |
Output is correct |
37 |
Correct |
941 ms |
157296 KB |
Output is correct |
38 |
Correct |
939 ms |
154976 KB |
Output is correct |
39 |
Correct |
616 ms |
153176 KB |
Output is correct |
40 |
Correct |
603 ms |
155288 KB |
Output is correct |
41 |
Correct |
660 ms |
94760 KB |
Output is correct |
42 |
Correct |
706 ms |
96284 KB |
Output is correct |
43 |
Correct |
83 ms |
35748 KB |
Output is correct |
44 |
Correct |
723 ms |
95964 KB |
Output is correct |
45 |
Correct |
709 ms |
96020 KB |
Output is correct |
46 |
Correct |
647 ms |
94228 KB |
Output is correct |
47 |
Correct |
363 ms |
90288 KB |
Output is correct |
48 |
Correct |
362 ms |
98892 KB |
Output is correct |
49 |
Correct |
420 ms |
98856 KB |
Output is correct |
50 |
Correct |
476 ms |
99312 KB |
Output is correct |
51 |
Correct |
466 ms |
99096 KB |
Output is correct |
52 |
Correct |
4070 ms |
316788 KB |
Output is correct |
53 |
Correct |
2665 ms |
328264 KB |
Output is correct |
54 |
Correct |
1176 ms |
129184 KB |
Output is correct |
55 |
Correct |
3687 ms |
312048 KB |
Output is correct |
56 |
Correct |
2047 ms |
323612 KB |
Output is correct |
57 |
Correct |
2405 ms |
325252 KB |
Output is correct |
58 |
Correct |
1162 ms |
130460 KB |
Output is correct |
59 |
Correct |
3757 ms |
310968 KB |
Output is correct |
60 |
Correct |
3494 ms |
319664 KB |
Output is correct |
61 |
Correct |
2623 ms |
320588 KB |
Output is correct |
62 |
Correct |
2234 ms |
318500 KB |
Output is correct |
63 |
Correct |
2317 ms |
319432 KB |
Output is correct |
64 |
Execution timed out |
5084 ms |
463148 KB |
Time limit exceeded |
65 |
Halted |
0 ms |
0 KB |
- |