#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=2e5+5;
const int K=1<<18;
const int inf=1e9;
int n,m,k,q;
int a[M],b[M],mn[N],mx[N];
void genmin(){
vector<int> st[N],ed[N];
for(int i=1;i<=m;i++){
if(a[i]<b[i])continue;
st[max(a[i]-k+1,b[i])].emplace_back(i);
ed[a[i]].emplace_back(i);
}
set<pair<int,int>> s;
for(int i=1;i<=n;i++){
for(auto j:st[i])s.emplace(b[j],j);
mn[i]=s.empty()?i:s.begin()->first;
for(auto j:ed[i])s.erase({b[j],j});
}
}
void genmax(){
vector<int> st[N],ed[N];
for(int i=1;i<=m;i++){
if(a[i]>b[i])continue;
st[a[i]].emplace_back(i);
ed[min(a[i]+k-1,b[i])].emplace_back(i);
}
set<pair<int,int>> s;
for(int i=1;i<=n;i++){
for(auto j:st[i])s.emplace(b[j],j);
mx[i]=s.empty()?i:s.rbegin()->first;
for(auto j:ed[i])s.erase({b[j],j});
}
}
struct segtree{
struct node{
int l,r;
node():l(inf),r(-inf){}
node(int i):l(i),r(i){}
node(int l,int r):l(l),r(r){}
friend node operator+(node a,node b){
return node(min(a.l,b.l),max(a.r,b.r));
}
}t[K];
void build(int l,int r,int i){
if(l==r)return void(t[i]=node(mn[l],mx[l]));
int m=(l+r)/2;
build(l,m,i*2);
build(m+1,r,i*2+1);
t[i]=t[i*2]+t[i*2+1];
}
void build(){
build(1,n,1);
}
node query(int l,int r,int i,int x,int y){
if(y<l||r<x)return node();
if(x<=l&&r<=y)return t[i];
int m=(l+r)/2;
return query(l,m,i*2,x,y)+query(m+1,r,i*2+1,x,y);
}
node query(int x,int y){
return query(1,n,1,x,y);
}
}s[20];
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> k >> m;
for(int i=1;i<=m;i++)cin >> a[i] >> b[i];
genmin();
genmax();
s[0].build();
for(int i=1;i<20;i++){
for(int j=1;j<=n;j++){
auto tmp=s[i-1].query(mn[j],mx[j]);
mn[j]=tmp.l,mx[j]=tmp.r;
}
s[i].build();
}
cin >> q;
while(q--){
int st,ed;
cin >> st >> ed;
int ans=0;
int cl=st,cr=st;
for(int i=19;i>=0;i--){
auto tmp=s[i].query(cl,cr);
if(tmp.l<=ed&&ed<=tmp.r)continue;
ans|=1<<i;
cl=tmp.l,cr=tmp.r;
}
cout << (++ans>m?-1:ans) << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
46036 KB |
Output is correct |
2 |
Correct |
21 ms |
46084 KB |
Output is correct |
3 |
Correct |
22 ms |
45956 KB |
Output is correct |
4 |
Correct |
21 ms |
45968 KB |
Output is correct |
5 |
Correct |
21 ms |
46036 KB |
Output is correct |
6 |
Correct |
21 ms |
46016 KB |
Output is correct |
7 |
Correct |
21 ms |
46012 KB |
Output is correct |
8 |
Correct |
21 ms |
46056 KB |
Output is correct |
9 |
Correct |
21 ms |
46036 KB |
Output is correct |
10 |
Correct |
23 ms |
46032 KB |
Output is correct |
11 |
Correct |
21 ms |
46008 KB |
Output is correct |
12 |
Correct |
21 ms |
45980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
46036 KB |
Output is correct |
2 |
Correct |
21 ms |
46084 KB |
Output is correct |
3 |
Correct |
22 ms |
45956 KB |
Output is correct |
4 |
Correct |
21 ms |
45968 KB |
Output is correct |
5 |
Correct |
21 ms |
46036 KB |
Output is correct |
6 |
Correct |
21 ms |
46016 KB |
Output is correct |
7 |
Correct |
21 ms |
46012 KB |
Output is correct |
8 |
Correct |
21 ms |
46056 KB |
Output is correct |
9 |
Correct |
21 ms |
46036 KB |
Output is correct |
10 |
Correct |
23 ms |
46032 KB |
Output is correct |
11 |
Correct |
21 ms |
46008 KB |
Output is correct |
12 |
Correct |
21 ms |
45980 KB |
Output is correct |
13 |
Correct |
26 ms |
46160 KB |
Output is correct |
14 |
Correct |
32 ms |
46176 KB |
Output is correct |
15 |
Correct |
24 ms |
46164 KB |
Output is correct |
16 |
Correct |
25 ms |
46028 KB |
Output is correct |
17 |
Correct |
30 ms |
46112 KB |
Output is correct |
18 |
Correct |
24 ms |
46128 KB |
Output is correct |
19 |
Correct |
27 ms |
46176 KB |
Output is correct |
20 |
Correct |
23 ms |
46120 KB |
Output is correct |
21 |
Correct |
22 ms |
46140 KB |
Output is correct |
22 |
Correct |
26 ms |
46052 KB |
Output is correct |
23 |
Correct |
27 ms |
46140 KB |
Output is correct |
24 |
Correct |
28 ms |
46136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
318 ms |
50596 KB |
Output is correct |
2 |
Correct |
286 ms |
50488 KB |
Output is correct |
3 |
Correct |
307 ms |
50712 KB |
Output is correct |
4 |
Correct |
287 ms |
50536 KB |
Output is correct |
5 |
Correct |
180 ms |
53848 KB |
Output is correct |
6 |
Correct |
320 ms |
56956 KB |
Output is correct |
7 |
Correct |
159 ms |
58672 KB |
Output is correct |
8 |
Correct |
92 ms |
52224 KB |
Output is correct |
9 |
Correct |
93 ms |
52240 KB |
Output is correct |
10 |
Correct |
294 ms |
54736 KB |
Output is correct |
11 |
Correct |
252 ms |
54728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
428 ms |
52068 KB |
Output is correct |
2 |
Correct |
438 ms |
53932 KB |
Output is correct |
3 |
Correct |
570 ms |
52616 KB |
Output is correct |
4 |
Correct |
249 ms |
59332 KB |
Output is correct |
5 |
Correct |
244 ms |
57172 KB |
Output is correct |
6 |
Correct |
241 ms |
57108 KB |
Output is correct |
7 |
Correct |
467 ms |
55336 KB |
Output is correct |
8 |
Correct |
439 ms |
55416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
516 ms |
57408 KB |
Output is correct |
2 |
Correct |
612 ms |
55752 KB |
Output is correct |
3 |
Correct |
630 ms |
51688 KB |
Output is correct |
4 |
Correct |
557 ms |
49196 KB |
Output is correct |
5 |
Correct |
441 ms |
47936 KB |
Output is correct |
6 |
Correct |
440 ms |
47648 KB |
Output is correct |
7 |
Correct |
343 ms |
57292 KB |
Output is correct |
8 |
Correct |
22 ms |
46036 KB |
Output is correct |
9 |
Correct |
30 ms |
46164 KB |
Output is correct |
10 |
Correct |
322 ms |
59116 KB |
Output is correct |
11 |
Correct |
382 ms |
61020 KB |
Output is correct |
12 |
Correct |
408 ms |
59168 KB |
Output is correct |
13 |
Correct |
429 ms |
60920 KB |
Output is correct |
14 |
Correct |
21 ms |
46036 KB |
Output is correct |
15 |
Correct |
27 ms |
46224 KB |
Output is correct |
16 |
Correct |
321 ms |
56384 KB |
Output is correct |
17 |
Correct |
598 ms |
57080 KB |
Output is correct |
18 |
Correct |
540 ms |
57080 KB |
Output is correct |
19 |
Correct |
512 ms |
56940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
46036 KB |
Output is correct |
2 |
Correct |
21 ms |
46084 KB |
Output is correct |
3 |
Correct |
22 ms |
45956 KB |
Output is correct |
4 |
Correct |
21 ms |
45968 KB |
Output is correct |
5 |
Correct |
21 ms |
46036 KB |
Output is correct |
6 |
Correct |
21 ms |
46016 KB |
Output is correct |
7 |
Correct |
21 ms |
46012 KB |
Output is correct |
8 |
Correct |
21 ms |
46056 KB |
Output is correct |
9 |
Correct |
21 ms |
46036 KB |
Output is correct |
10 |
Correct |
23 ms |
46032 KB |
Output is correct |
11 |
Correct |
21 ms |
46008 KB |
Output is correct |
12 |
Correct |
21 ms |
45980 KB |
Output is correct |
13 |
Correct |
26 ms |
46160 KB |
Output is correct |
14 |
Correct |
32 ms |
46176 KB |
Output is correct |
15 |
Correct |
24 ms |
46164 KB |
Output is correct |
16 |
Correct |
25 ms |
46028 KB |
Output is correct |
17 |
Correct |
30 ms |
46112 KB |
Output is correct |
18 |
Correct |
24 ms |
46128 KB |
Output is correct |
19 |
Correct |
27 ms |
46176 KB |
Output is correct |
20 |
Correct |
23 ms |
46120 KB |
Output is correct |
21 |
Correct |
22 ms |
46140 KB |
Output is correct |
22 |
Correct |
26 ms |
46052 KB |
Output is correct |
23 |
Correct |
27 ms |
46140 KB |
Output is correct |
24 |
Correct |
28 ms |
46136 KB |
Output is correct |
25 |
Correct |
318 ms |
50596 KB |
Output is correct |
26 |
Correct |
286 ms |
50488 KB |
Output is correct |
27 |
Correct |
307 ms |
50712 KB |
Output is correct |
28 |
Correct |
287 ms |
50536 KB |
Output is correct |
29 |
Correct |
180 ms |
53848 KB |
Output is correct |
30 |
Correct |
320 ms |
56956 KB |
Output is correct |
31 |
Correct |
159 ms |
58672 KB |
Output is correct |
32 |
Correct |
92 ms |
52224 KB |
Output is correct |
33 |
Correct |
93 ms |
52240 KB |
Output is correct |
34 |
Correct |
294 ms |
54736 KB |
Output is correct |
35 |
Correct |
252 ms |
54728 KB |
Output is correct |
36 |
Correct |
428 ms |
52068 KB |
Output is correct |
37 |
Correct |
438 ms |
53932 KB |
Output is correct |
38 |
Correct |
570 ms |
52616 KB |
Output is correct |
39 |
Correct |
249 ms |
59332 KB |
Output is correct |
40 |
Correct |
244 ms |
57172 KB |
Output is correct |
41 |
Correct |
241 ms |
57108 KB |
Output is correct |
42 |
Correct |
467 ms |
55336 KB |
Output is correct |
43 |
Correct |
439 ms |
55416 KB |
Output is correct |
44 |
Correct |
516 ms |
57408 KB |
Output is correct |
45 |
Correct |
612 ms |
55752 KB |
Output is correct |
46 |
Correct |
630 ms |
51688 KB |
Output is correct |
47 |
Correct |
557 ms |
49196 KB |
Output is correct |
48 |
Correct |
441 ms |
47936 KB |
Output is correct |
49 |
Correct |
440 ms |
47648 KB |
Output is correct |
50 |
Correct |
343 ms |
57292 KB |
Output is correct |
51 |
Correct |
22 ms |
46036 KB |
Output is correct |
52 |
Correct |
30 ms |
46164 KB |
Output is correct |
53 |
Correct |
322 ms |
59116 KB |
Output is correct |
54 |
Correct |
382 ms |
61020 KB |
Output is correct |
55 |
Correct |
408 ms |
59168 KB |
Output is correct |
56 |
Correct |
429 ms |
60920 KB |
Output is correct |
57 |
Correct |
21 ms |
46036 KB |
Output is correct |
58 |
Correct |
27 ms |
46224 KB |
Output is correct |
59 |
Correct |
321 ms |
56384 KB |
Output is correct |
60 |
Correct |
598 ms |
57080 KB |
Output is correct |
61 |
Correct |
540 ms |
57080 KB |
Output is correct |
62 |
Correct |
512 ms |
56940 KB |
Output is correct |
63 |
Correct |
511 ms |
52084 KB |
Output is correct |
64 |
Correct |
599 ms |
52472 KB |
Output is correct |
65 |
Correct |
515 ms |
52248 KB |
Output is correct |
66 |
Correct |
212 ms |
56080 KB |
Output is correct |
67 |
Correct |
493 ms |
57700 KB |
Output is correct |
68 |
Correct |
415 ms |
55380 KB |
Output is correct |
69 |
Correct |
250 ms |
57208 KB |
Output is correct |
70 |
Correct |
499 ms |
55448 KB |
Output is correct |
71 |
Correct |
524 ms |
55404 KB |
Output is correct |