#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
int n,k;
vector<int> maxr;
vector<int> minl;
void setr(int l,int r,int v){
l+=n;r+=n;
while(r>l){
if(l&1) {maxr[l] = max(maxr[l],v);l++;}
if(r&1) {r--;maxr[r] = max(maxr[r],v);}
l>>=1;r>>=1;
}
}
void setl(int l,int r,int v){
l+=n;r+=n;
while(r>l){
if(l&1) {minl[l] = min(minl[l],v);l++;}
if(r&1) {r--;minl[r] = min(minl[r],v);}
l>>=1;r>>=1;
}
}
struct segtree{
vector<pair<int,int> > seg;
void init(){
seg.resize(2*n);
}
pair<int,int> mix(pair<int,int> a,pair<int,int> b){
return {min(a.first,b.first),max(a.second,b.second)};
}
void built(int ind){
if(2*ind+1>=2*n) return ;
built(2*ind);built(2*ind+1);
seg[ind] = mix(seg[2*ind],seg[2*ind+1]);
}
void modify(int ind,pair<int,int> v){
ind+=n;
while(ind){
seg[ind] = mix(seg[ind],v);
ind>>=1;
}
}
pair<int,int> query(int l,int r){
l+=n;r+=n;
pair<int,int> ans = {1e9,-1};
while(r>l){
if(l&1) ans = mix(ans,seg[l++]);
if(r&1) ans = mix(ans,seg[--r]);
l>>=1;r>>=1;
}
return ans;
}
};
vector<segtree> jump;
int main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
int m;cin>>m;
maxr.resize(2*n,0);
minl.resize(2*n,0);
for(int i=0;i<n;i++){
maxr[i] = -1;
minl[i] = 1e9;
maxr[i+n]=i;
minl[i+n]=i;
}
jump.resize(18);
for(int i=0;i<m;i++){
int a,b;cin>>a>>b;
a--;b--;
if(a<b){
setr(a,min(a+k,b+1),b);
}else{
setl(max(a-k+1,b),a+1,b);
}
}
for(int i=0;i<n;i++){
int g = i+n;
while(g){
maxr[i+n] = max(maxr[i+n],maxr[g]);
minl[i+n] = min(minl[i+n],minl[g]);
g>>=1;
}
}
jump[0].init();
for(int i=0;i<n;i++){
jump[0].seg[i+n] = {minl[i+n],maxr[i+n]};
}
jump[0].built(1);
for(int j=1;j<18;j++){
jump[j].init();
for(int i=0;i<n;i++){
pair<int,int> prevrange = jump[j-1].seg[i+n];
jump[j].seg[i+n] = jump[j-1].query(prevrange.first,prevrange.second+1);
}
jump[j].built(1);
}
/* for(int j=0;j<18;j++){
for(int i=0;i<n;i++){
cout<<jump[j].seg[i+n].first<<"~"<<jump[j].seg[i+n].second<<"|";
}
cout<<"\n";
}*/
int q;cin>>q;
while(q--){
int a,b;cin>>a>>b;
a--;b--;
ll ans =0;
if(b>jump[17].seg[a+n].second || b<jump[17].seg[a+n].first){cout<<-1<<"\n";continue;}
int l = a;int r = a;
for(int p=17;p>=0;p--){
pair<int,int> range = jump[p].query(l,r+1);
if(b<range.first || b>range.second){
l = range.first;
r = range.second;
ans+=(1<<p);
}
}
cout<<ans+1<<"\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
1 ms |
324 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
324 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
1 ms |
324 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
324 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
360 KB |
Output is correct |
13 |
Correct |
5 ms |
844 KB |
Output is correct |
14 |
Correct |
5 ms |
840 KB |
Output is correct |
15 |
Correct |
3 ms |
852 KB |
Output is correct |
16 |
Correct |
3 ms |
852 KB |
Output is correct |
17 |
Correct |
3 ms |
840 KB |
Output is correct |
18 |
Correct |
3 ms |
852 KB |
Output is correct |
19 |
Correct |
3 ms |
848 KB |
Output is correct |
20 |
Correct |
3 ms |
852 KB |
Output is correct |
21 |
Correct |
2 ms |
884 KB |
Output is correct |
22 |
Correct |
3 ms |
860 KB |
Output is correct |
23 |
Correct |
3 ms |
852 KB |
Output is correct |
24 |
Correct |
3 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
30948 KB |
Output is correct |
2 |
Correct |
143 ms |
30916 KB |
Output is correct |
3 |
Correct |
175 ms |
31116 KB |
Output is correct |
4 |
Correct |
146 ms |
30924 KB |
Output is correct |
5 |
Correct |
178 ms |
32276 KB |
Output is correct |
6 |
Correct |
119 ms |
32308 KB |
Output is correct |
7 |
Correct |
142 ms |
32092 KB |
Output is correct |
8 |
Correct |
101 ms |
30916 KB |
Output is correct |
9 |
Correct |
104 ms |
31244 KB |
Output is correct |
10 |
Correct |
135 ms |
32460 KB |
Output is correct |
11 |
Correct |
133 ms |
32360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
161 ms |
31696 KB |
Output is correct |
2 |
Correct |
153 ms |
33100 KB |
Output is correct |
3 |
Correct |
200 ms |
31996 KB |
Output is correct |
4 |
Correct |
145 ms |
32744 KB |
Output is correct |
5 |
Correct |
175 ms |
32624 KB |
Output is correct |
6 |
Correct |
145 ms |
32856 KB |
Output is correct |
7 |
Correct |
165 ms |
32976 KB |
Output is correct |
8 |
Correct |
216 ms |
33104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
33132 KB |
Output is correct |
2 |
Correct |
238 ms |
32096 KB |
Output is correct |
3 |
Correct |
229 ms |
31436 KB |
Output is correct |
4 |
Correct |
221 ms |
31068 KB |
Output is correct |
5 |
Correct |
142 ms |
30784 KB |
Output is correct |
6 |
Correct |
202 ms |
30688 KB |
Output is correct |
7 |
Correct |
177 ms |
31948 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
4 ms |
844 KB |
Output is correct |
10 |
Correct |
186 ms |
32308 KB |
Output is correct |
11 |
Correct |
207 ms |
32972 KB |
Output is correct |
12 |
Correct |
205 ms |
32580 KB |
Output is correct |
13 |
Correct |
228 ms |
32876 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
4 ms |
844 KB |
Output is correct |
16 |
Correct |
150 ms |
32348 KB |
Output is correct |
17 |
Correct |
272 ms |
33156 KB |
Output is correct |
18 |
Correct |
256 ms |
33228 KB |
Output is correct |
19 |
Correct |
263 ms |
33140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
1 ms |
324 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
324 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
360 KB |
Output is correct |
13 |
Correct |
5 ms |
844 KB |
Output is correct |
14 |
Correct |
5 ms |
840 KB |
Output is correct |
15 |
Correct |
3 ms |
852 KB |
Output is correct |
16 |
Correct |
3 ms |
852 KB |
Output is correct |
17 |
Correct |
3 ms |
840 KB |
Output is correct |
18 |
Correct |
3 ms |
852 KB |
Output is correct |
19 |
Correct |
3 ms |
848 KB |
Output is correct |
20 |
Correct |
3 ms |
852 KB |
Output is correct |
21 |
Correct |
2 ms |
884 KB |
Output is correct |
22 |
Correct |
3 ms |
860 KB |
Output is correct |
23 |
Correct |
3 ms |
852 KB |
Output is correct |
24 |
Correct |
3 ms |
852 KB |
Output is correct |
25 |
Correct |
178 ms |
30948 KB |
Output is correct |
26 |
Correct |
143 ms |
30916 KB |
Output is correct |
27 |
Correct |
175 ms |
31116 KB |
Output is correct |
28 |
Correct |
146 ms |
30924 KB |
Output is correct |
29 |
Correct |
178 ms |
32276 KB |
Output is correct |
30 |
Correct |
119 ms |
32308 KB |
Output is correct |
31 |
Correct |
142 ms |
32092 KB |
Output is correct |
32 |
Correct |
101 ms |
30916 KB |
Output is correct |
33 |
Correct |
104 ms |
31244 KB |
Output is correct |
34 |
Correct |
135 ms |
32460 KB |
Output is correct |
35 |
Correct |
133 ms |
32360 KB |
Output is correct |
36 |
Correct |
161 ms |
31696 KB |
Output is correct |
37 |
Correct |
153 ms |
33100 KB |
Output is correct |
38 |
Correct |
200 ms |
31996 KB |
Output is correct |
39 |
Correct |
145 ms |
32744 KB |
Output is correct |
40 |
Correct |
175 ms |
32624 KB |
Output is correct |
41 |
Correct |
145 ms |
32856 KB |
Output is correct |
42 |
Correct |
165 ms |
32976 KB |
Output is correct |
43 |
Correct |
216 ms |
33104 KB |
Output is correct |
44 |
Correct |
189 ms |
33132 KB |
Output is correct |
45 |
Correct |
238 ms |
32096 KB |
Output is correct |
46 |
Correct |
229 ms |
31436 KB |
Output is correct |
47 |
Correct |
221 ms |
31068 KB |
Output is correct |
48 |
Correct |
142 ms |
30784 KB |
Output is correct |
49 |
Correct |
202 ms |
30688 KB |
Output is correct |
50 |
Correct |
177 ms |
31948 KB |
Output is correct |
51 |
Correct |
1 ms |
340 KB |
Output is correct |
52 |
Correct |
4 ms |
844 KB |
Output is correct |
53 |
Correct |
186 ms |
32308 KB |
Output is correct |
54 |
Correct |
207 ms |
32972 KB |
Output is correct |
55 |
Correct |
205 ms |
32580 KB |
Output is correct |
56 |
Correct |
228 ms |
32876 KB |
Output is correct |
57 |
Correct |
1 ms |
340 KB |
Output is correct |
58 |
Correct |
4 ms |
844 KB |
Output is correct |
59 |
Correct |
150 ms |
32348 KB |
Output is correct |
60 |
Correct |
272 ms |
33156 KB |
Output is correct |
61 |
Correct |
256 ms |
33228 KB |
Output is correct |
62 |
Correct |
263 ms |
33140 KB |
Output is correct |
63 |
Correct |
231 ms |
31612 KB |
Output is correct |
64 |
Correct |
265 ms |
31964 KB |
Output is correct |
65 |
Correct |
250 ms |
31708 KB |
Output is correct |
66 |
Correct |
150 ms |
33112 KB |
Output is correct |
67 |
Correct |
230 ms |
33136 KB |
Output is correct |
68 |
Correct |
164 ms |
32680 KB |
Output is correct |
69 |
Correct |
145 ms |
32860 KB |
Output is correct |
70 |
Correct |
176 ms |
33052 KB |
Output is correct |
71 |
Correct |
221 ms |
33272 KB |
Output is correct |