#include <bits/stdc++.h>
using namespace std;
const int N = 505;
struct segtree{
int n, tl, tr, type;
vector<int> st, a;
int merge(int x, int y){
if(type==0) return min(x, y);
return max(x, y);
}
segtree(vector<int> x, int t){
n=x.size(); type = t;
a=x; st.resize(2*n);
for(int i=0; i<n; i++) st[i+n]=x[i];
for(int i=n-1; i>=0; i--) st[i]=merge(st[i*2], st[i*2+1]);
}
int operator()(int l, int r){
int base=a[l];
for(l+=n, r+=n+1; l!=r; l/=2, r/=2){
if(l&1) base=merge(base, st[l++]);
if(r&1) base=merge(base, st[--r]);
}
return base;
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k, m; cin >> n >> k >> m;
vector<int> l(n), r(n);
priority_queue<array<int, 2>> q;
iota(l.begin(), l.end(), 0);
iota(r.begin(), r.end(), 0);
vector<array<int, 2>> e(m);
for(auto &[i, l]: e) cin >> i >> l, i--, l--;
sort(e.begin(), e.end());
int pos=0;
for(int i=0; i<n; i++){
while(pos<m && e[pos][0]==i)
q.push({e[pos][1], e[pos][0]}), pos++;
while(q.size()&&q.top()[1] < i-k+1)
q.pop();
if(q.size())
if(q.size()) r[i]=max(r[i], q.top()[0]);
}
while(q.size()) q.pop();
reverse(e.begin(), e.end());
pos = 0;
for(int i=n-1; i>=0; i--){
while(pos<m && e[pos][0]==i)
q.push({-e[pos][1], e[pos][0]}), pos++;
while(q.size()&&q.top()[1] > i+k-1)
q.pop();
if(q.size()) l[i]=min(l[i], -q.top()[0]);
}
vector<vector<int>> left, right;
left.push_back(l);
right.push_back(r);
vector<segtree> left_st, right_st;
for(int i=1; i<=n; i*=2){
segtree l(left.back(), 0), r(right.back(), 1);
vector<int> l_new(n), r_new(n);
for(int i=0; i<n; i++){
l_new[i]=l(left.back()[i], right.back()[i]);
r_new[i]=r(left.back()[i], right.back()[i]);
}
left_st.push_back(l); right_st.push_back(r);
left.push_back(l_new);
right.push_back(r_new);
}
int qe; cin >> qe;
while(qe--){
int x, y; cin >> x >> y;
x--; y--;
int s=0;
int le=-1, re=-1, pos=-1, ans=0;
for(int i=left.size()-1; i>=0; i--){
int tl=left[i][x], tr=right[i][x];
if(tl<= y&&y<=tr)
continue;
else{
le=tl; re=tr;
pos=i; ans+=(1<<i);
break;
}
}
if(le==-1 && re==-1) cout<<1<<"\n";
else{
for(int i=pos-1; i>=0; i--){
int vl=left_st[i](le, re), vr=right_st[i](le, re);
if(vl <= y && y<=vr){
continue;
}
else{
le=min(vl, le); re=max(re, vr);
ans+=(1<<i);
}
}
ans++;
int tl=(left_st[0](le, re));
int tr=right_st[0](le, re);
if(tl<=y&&y<=tr) cout<<ans<<"\n";
else cout<<-1<<"\n";
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:103:13: warning: unused variable 's' [-Wunused-variable]
103 | int s=0;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
452 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
452 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
6 ms |
1116 KB |
Output is correct |
14 |
Correct |
5 ms |
1116 KB |
Output is correct |
15 |
Correct |
3 ms |
1092 KB |
Output is correct |
16 |
Correct |
4 ms |
1116 KB |
Output is correct |
17 |
Correct |
3 ms |
1112 KB |
Output is correct |
18 |
Correct |
3 ms |
1116 KB |
Output is correct |
19 |
Correct |
2 ms |
1240 KB |
Output is correct |
20 |
Correct |
2 ms |
1116 KB |
Output is correct |
21 |
Correct |
2 ms |
1116 KB |
Output is correct |
22 |
Correct |
3 ms |
1116 KB |
Output is correct |
23 |
Correct |
3 ms |
1116 KB |
Output is correct |
24 |
Correct |
3 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
232 ms |
59940 KB |
Output is correct |
2 |
Correct |
238 ms |
59808 KB |
Output is correct |
3 |
Correct |
285 ms |
60164 KB |
Output is correct |
4 |
Correct |
212 ms |
59716 KB |
Output is correct |
5 |
Correct |
195 ms |
63688 KB |
Output is correct |
6 |
Correct |
225 ms |
63676 KB |
Output is correct |
7 |
Correct |
191 ms |
63380 KB |
Output is correct |
8 |
Correct |
170 ms |
60476 KB |
Output is correct |
9 |
Correct |
178 ms |
60932 KB |
Output is correct |
10 |
Correct |
231 ms |
63616 KB |
Output is correct |
11 |
Correct |
215 ms |
63588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
283 ms |
61068 KB |
Output is correct |
2 |
Correct |
274 ms |
64516 KB |
Output is correct |
3 |
Correct |
414 ms |
61860 KB |
Output is correct |
4 |
Correct |
216 ms |
63944 KB |
Output is correct |
5 |
Correct |
216 ms |
63688 KB |
Output is correct |
6 |
Correct |
217 ms |
64456 KB |
Output is correct |
7 |
Correct |
287 ms |
64488 KB |
Output is correct |
8 |
Correct |
364 ms |
64488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
601 ms |
64460 KB |
Output is correct |
2 |
Correct |
511 ms |
62476 KB |
Output is correct |
3 |
Correct |
440 ms |
60448 KB |
Output is correct |
4 |
Correct |
450 ms |
59776 KB |
Output is correct |
5 |
Correct |
250 ms |
59168 KB |
Output is correct |
6 |
Correct |
370 ms |
59136 KB |
Output is correct |
7 |
Correct |
318 ms |
61788 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
4 ms |
1116 KB |
Output is correct |
10 |
Correct |
349 ms |
63604 KB |
Output is correct |
11 |
Correct |
359 ms |
64396 KB |
Output is correct |
12 |
Correct |
352 ms |
63692 KB |
Output is correct |
13 |
Correct |
370 ms |
64204 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
5 ms |
1116 KB |
Output is correct |
16 |
Correct |
292 ms |
62144 KB |
Output is correct |
17 |
Correct |
537 ms |
64508 KB |
Output is correct |
18 |
Correct |
487 ms |
64460 KB |
Output is correct |
19 |
Correct |
515 ms |
64468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
452 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
6 ms |
1116 KB |
Output is correct |
14 |
Correct |
5 ms |
1116 KB |
Output is correct |
15 |
Correct |
3 ms |
1092 KB |
Output is correct |
16 |
Correct |
4 ms |
1116 KB |
Output is correct |
17 |
Correct |
3 ms |
1112 KB |
Output is correct |
18 |
Correct |
3 ms |
1116 KB |
Output is correct |
19 |
Correct |
2 ms |
1240 KB |
Output is correct |
20 |
Correct |
2 ms |
1116 KB |
Output is correct |
21 |
Correct |
2 ms |
1116 KB |
Output is correct |
22 |
Correct |
3 ms |
1116 KB |
Output is correct |
23 |
Correct |
3 ms |
1116 KB |
Output is correct |
24 |
Correct |
3 ms |
1116 KB |
Output is correct |
25 |
Correct |
232 ms |
59940 KB |
Output is correct |
26 |
Correct |
238 ms |
59808 KB |
Output is correct |
27 |
Correct |
285 ms |
60164 KB |
Output is correct |
28 |
Correct |
212 ms |
59716 KB |
Output is correct |
29 |
Correct |
195 ms |
63688 KB |
Output is correct |
30 |
Correct |
225 ms |
63676 KB |
Output is correct |
31 |
Correct |
191 ms |
63380 KB |
Output is correct |
32 |
Correct |
170 ms |
60476 KB |
Output is correct |
33 |
Correct |
178 ms |
60932 KB |
Output is correct |
34 |
Correct |
231 ms |
63616 KB |
Output is correct |
35 |
Correct |
215 ms |
63588 KB |
Output is correct |
36 |
Correct |
283 ms |
61068 KB |
Output is correct |
37 |
Correct |
274 ms |
64516 KB |
Output is correct |
38 |
Correct |
414 ms |
61860 KB |
Output is correct |
39 |
Correct |
216 ms |
63944 KB |
Output is correct |
40 |
Correct |
216 ms |
63688 KB |
Output is correct |
41 |
Correct |
217 ms |
64456 KB |
Output is correct |
42 |
Correct |
287 ms |
64488 KB |
Output is correct |
43 |
Correct |
364 ms |
64488 KB |
Output is correct |
44 |
Correct |
601 ms |
64460 KB |
Output is correct |
45 |
Correct |
511 ms |
62476 KB |
Output is correct |
46 |
Correct |
440 ms |
60448 KB |
Output is correct |
47 |
Correct |
450 ms |
59776 KB |
Output is correct |
48 |
Correct |
250 ms |
59168 KB |
Output is correct |
49 |
Correct |
370 ms |
59136 KB |
Output is correct |
50 |
Correct |
318 ms |
61788 KB |
Output is correct |
51 |
Correct |
1 ms |
348 KB |
Output is correct |
52 |
Correct |
4 ms |
1116 KB |
Output is correct |
53 |
Correct |
349 ms |
63604 KB |
Output is correct |
54 |
Correct |
359 ms |
64396 KB |
Output is correct |
55 |
Correct |
352 ms |
63692 KB |
Output is correct |
56 |
Correct |
370 ms |
64204 KB |
Output is correct |
57 |
Correct |
1 ms |
344 KB |
Output is correct |
58 |
Correct |
5 ms |
1116 KB |
Output is correct |
59 |
Correct |
292 ms |
62144 KB |
Output is correct |
60 |
Correct |
537 ms |
64508 KB |
Output is correct |
61 |
Correct |
487 ms |
64460 KB |
Output is correct |
62 |
Correct |
515 ms |
64468 KB |
Output is correct |
63 |
Correct |
460 ms |
60960 KB |
Output is correct |
64 |
Correct |
578 ms |
60964 KB |
Output is correct |
65 |
Correct |
470 ms |
60668 KB |
Output is correct |
66 |
Correct |
255 ms |
64452 KB |
Output is correct |
67 |
Correct |
449 ms |
64360 KB |
Output is correct |
68 |
Correct |
219 ms |
63692 KB |
Output is correct |
69 |
Correct |
213 ms |
64316 KB |
Output is correct |
70 |
Correct |
361 ms |
62960 KB |
Output is correct |
71 |
Correct |
411 ms |
64568 KB |
Output is correct |