#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;
if(ed<mn[st]||mx[st]<ed){
cout << -1 << "\n";
continue;
}
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+1 << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
46036 KB |
Output is correct |
2 |
Correct |
21 ms |
46084 KB |
Output is correct |
3 |
Correct |
21 ms |
45968 KB |
Output is correct |
4 |
Correct |
21 ms |
45980 KB |
Output is correct |
5 |
Correct |
22 ms |
45972 KB |
Output is correct |
6 |
Correct |
21 ms |
46036 KB |
Output is correct |
7 |
Correct |
24 ms |
46088 KB |
Output is correct |
8 |
Correct |
21 ms |
46060 KB |
Output is correct |
9 |
Correct |
21 ms |
46036 KB |
Output is correct |
10 |
Correct |
27 ms |
46036 KB |
Output is correct |
11 |
Correct |
21 ms |
46032 KB |
Output is correct |
12 |
Correct |
21 ms |
46036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
46036 KB |
Output is correct |
2 |
Correct |
21 ms |
46084 KB |
Output is correct |
3 |
Correct |
21 ms |
45968 KB |
Output is correct |
4 |
Correct |
21 ms |
45980 KB |
Output is correct |
5 |
Correct |
22 ms |
45972 KB |
Output is correct |
6 |
Correct |
21 ms |
46036 KB |
Output is correct |
7 |
Correct |
24 ms |
46088 KB |
Output is correct |
8 |
Correct |
21 ms |
46060 KB |
Output is correct |
9 |
Correct |
21 ms |
46036 KB |
Output is correct |
10 |
Correct |
27 ms |
46036 KB |
Output is correct |
11 |
Correct |
21 ms |
46032 KB |
Output is correct |
12 |
Correct |
21 ms |
46036 KB |
Output is correct |
13 |
Correct |
26 ms |
46124 KB |
Output is correct |
14 |
Correct |
27 ms |
46064 KB |
Output is correct |
15 |
Correct |
23 ms |
46060 KB |
Output is correct |
16 |
Correct |
23 ms |
46164 KB |
Output is correct |
17 |
Correct |
26 ms |
46080 KB |
Output is correct |
18 |
Correct |
26 ms |
46164 KB |
Output is correct |
19 |
Correct |
25 ms |
46108 KB |
Output is correct |
20 |
Correct |
25 ms |
46052 KB |
Output is correct |
21 |
Correct |
22 ms |
46080 KB |
Output is correct |
22 |
Correct |
26 ms |
46064 KB |
Output is correct |
23 |
Correct |
29 ms |
46060 KB |
Output is correct |
24 |
Correct |
27 ms |
46144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
316 ms |
50556 KB |
Output is correct |
2 |
Correct |
280 ms |
50604 KB |
Output is correct |
3 |
Correct |
342 ms |
50668 KB |
Output is correct |
4 |
Correct |
275 ms |
50532 KB |
Output is correct |
5 |
Correct |
168 ms |
53156 KB |
Output is correct |
6 |
Correct |
335 ms |
54652 KB |
Output is correct |
7 |
Correct |
158 ms |
56688 KB |
Output is correct |
8 |
Correct |
96 ms |
50984 KB |
Output is correct |
9 |
Correct |
100 ms |
51068 KB |
Output is correct |
10 |
Correct |
316 ms |
52392 KB |
Output is correct |
11 |
Correct |
263 ms |
52428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
385 ms |
52148 KB |
Output is correct |
2 |
Correct |
294 ms |
53288 KB |
Output is correct |
3 |
Correct |
558 ms |
50992 KB |
Output is correct |
4 |
Correct |
247 ms |
56820 KB |
Output is correct |
5 |
Correct |
251 ms |
54364 KB |
Output is correct |
6 |
Correct |
248 ms |
54408 KB |
Output is correct |
7 |
Correct |
492 ms |
52576 KB |
Output is correct |
8 |
Correct |
429 ms |
52524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
328 ms |
56156 KB |
Output is correct |
2 |
Correct |
646 ms |
54156 KB |
Output is correct |
3 |
Correct |
568 ms |
50616 KB |
Output is correct |
4 |
Correct |
552 ms |
48472 KB |
Output is correct |
5 |
Correct |
422 ms |
47300 KB |
Output is correct |
6 |
Correct |
433 ms |
47020 KB |
Output is correct |
7 |
Correct |
345 ms |
55804 KB |
Output is correct |
8 |
Correct |
22 ms |
46000 KB |
Output is correct |
9 |
Correct |
26 ms |
46176 KB |
Output is correct |
10 |
Correct |
335 ms |
56744 KB |
Output is correct |
11 |
Correct |
383 ms |
58284 KB |
Output is correct |
12 |
Correct |
413 ms |
56432 KB |
Output is correct |
13 |
Correct |
407 ms |
58140 KB |
Output is correct |
14 |
Correct |
22 ms |
46028 KB |
Output is correct |
15 |
Correct |
32 ms |
46124 KB |
Output is correct |
16 |
Correct |
319 ms |
54036 KB |
Output is correct |
17 |
Correct |
557 ms |
54236 KB |
Output is correct |
18 |
Correct |
559 ms |
54268 KB |
Output is correct |
19 |
Correct |
484 ms |
54120 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
46036 KB |
Output is correct |
2 |
Correct |
21 ms |
46084 KB |
Output is correct |
3 |
Correct |
21 ms |
45968 KB |
Output is correct |
4 |
Correct |
21 ms |
45980 KB |
Output is correct |
5 |
Correct |
22 ms |
45972 KB |
Output is correct |
6 |
Correct |
21 ms |
46036 KB |
Output is correct |
7 |
Correct |
24 ms |
46088 KB |
Output is correct |
8 |
Correct |
21 ms |
46060 KB |
Output is correct |
9 |
Correct |
21 ms |
46036 KB |
Output is correct |
10 |
Correct |
27 ms |
46036 KB |
Output is correct |
11 |
Correct |
21 ms |
46032 KB |
Output is correct |
12 |
Correct |
21 ms |
46036 KB |
Output is correct |
13 |
Correct |
26 ms |
46124 KB |
Output is correct |
14 |
Correct |
27 ms |
46064 KB |
Output is correct |
15 |
Correct |
23 ms |
46060 KB |
Output is correct |
16 |
Correct |
23 ms |
46164 KB |
Output is correct |
17 |
Correct |
26 ms |
46080 KB |
Output is correct |
18 |
Correct |
26 ms |
46164 KB |
Output is correct |
19 |
Correct |
25 ms |
46108 KB |
Output is correct |
20 |
Correct |
25 ms |
46052 KB |
Output is correct |
21 |
Correct |
22 ms |
46080 KB |
Output is correct |
22 |
Correct |
26 ms |
46064 KB |
Output is correct |
23 |
Correct |
29 ms |
46060 KB |
Output is correct |
24 |
Correct |
27 ms |
46144 KB |
Output is correct |
25 |
Correct |
316 ms |
50556 KB |
Output is correct |
26 |
Correct |
280 ms |
50604 KB |
Output is correct |
27 |
Correct |
342 ms |
50668 KB |
Output is correct |
28 |
Correct |
275 ms |
50532 KB |
Output is correct |
29 |
Correct |
168 ms |
53156 KB |
Output is correct |
30 |
Correct |
335 ms |
54652 KB |
Output is correct |
31 |
Correct |
158 ms |
56688 KB |
Output is correct |
32 |
Correct |
96 ms |
50984 KB |
Output is correct |
33 |
Correct |
100 ms |
51068 KB |
Output is correct |
34 |
Correct |
316 ms |
52392 KB |
Output is correct |
35 |
Correct |
263 ms |
52428 KB |
Output is correct |
36 |
Correct |
385 ms |
52148 KB |
Output is correct |
37 |
Correct |
294 ms |
53288 KB |
Output is correct |
38 |
Correct |
558 ms |
50992 KB |
Output is correct |
39 |
Correct |
247 ms |
56820 KB |
Output is correct |
40 |
Correct |
251 ms |
54364 KB |
Output is correct |
41 |
Correct |
248 ms |
54408 KB |
Output is correct |
42 |
Correct |
492 ms |
52576 KB |
Output is correct |
43 |
Correct |
429 ms |
52524 KB |
Output is correct |
44 |
Correct |
328 ms |
56156 KB |
Output is correct |
45 |
Correct |
646 ms |
54156 KB |
Output is correct |
46 |
Correct |
568 ms |
50616 KB |
Output is correct |
47 |
Correct |
552 ms |
48472 KB |
Output is correct |
48 |
Correct |
422 ms |
47300 KB |
Output is correct |
49 |
Correct |
433 ms |
47020 KB |
Output is correct |
50 |
Correct |
345 ms |
55804 KB |
Output is correct |
51 |
Correct |
22 ms |
46000 KB |
Output is correct |
52 |
Correct |
26 ms |
46176 KB |
Output is correct |
53 |
Correct |
335 ms |
56744 KB |
Output is correct |
54 |
Correct |
383 ms |
58284 KB |
Output is correct |
55 |
Correct |
413 ms |
56432 KB |
Output is correct |
56 |
Correct |
407 ms |
58140 KB |
Output is correct |
57 |
Correct |
22 ms |
46028 KB |
Output is correct |
58 |
Correct |
32 ms |
46124 KB |
Output is correct |
59 |
Correct |
319 ms |
54036 KB |
Output is correct |
60 |
Correct |
557 ms |
54236 KB |
Output is correct |
61 |
Correct |
559 ms |
54268 KB |
Output is correct |
62 |
Correct |
484 ms |
54120 KB |
Output is correct |
63 |
Correct |
476 ms |
50736 KB |
Output is correct |
64 |
Correct |
575 ms |
50920 KB |
Output is correct |
65 |
Correct |
484 ms |
50800 KB |
Output is correct |
66 |
Correct |
161 ms |
53180 KB |
Output is correct |
67 |
Correct |
522 ms |
54912 KB |
Output is correct |
68 |
Correct |
393 ms |
52584 KB |
Output is correct |
69 |
Correct |
241 ms |
54316 KB |
Output is correct |
70 |
Correct |
385 ms |
52604 KB |
Output is correct |
71 |
Correct |
515 ms |
52584 KB |
Output is correct |