#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int K=1<<18;
const int inf=1e9;
int n,m,k,q;
int a[N],b[N],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 |
22 ms |
45976 KB |
Output is correct |
2 |
Correct |
23 ms |
46028 KB |
Output is correct |
3 |
Correct |
20 ms |
45964 KB |
Output is correct |
4 |
Correct |
21 ms |
46092 KB |
Output is correct |
5 |
Correct |
21 ms |
46036 KB |
Output is correct |
6 |
Correct |
24 ms |
45976 KB |
Output is correct |
7 |
Correct |
22 ms |
45980 KB |
Output is correct |
8 |
Correct |
21 ms |
46044 KB |
Output is correct |
9 |
Correct |
21 ms |
46036 KB |
Output is correct |
10 |
Correct |
21 ms |
46036 KB |
Output is correct |
11 |
Correct |
22 ms |
46044 KB |
Output is correct |
12 |
Correct |
22 ms |
46036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
45976 KB |
Output is correct |
2 |
Correct |
23 ms |
46028 KB |
Output is correct |
3 |
Correct |
20 ms |
45964 KB |
Output is correct |
4 |
Correct |
21 ms |
46092 KB |
Output is correct |
5 |
Correct |
21 ms |
46036 KB |
Output is correct |
6 |
Correct |
24 ms |
45976 KB |
Output is correct |
7 |
Correct |
22 ms |
45980 KB |
Output is correct |
8 |
Correct |
21 ms |
46044 KB |
Output is correct |
9 |
Correct |
21 ms |
46036 KB |
Output is correct |
10 |
Correct |
21 ms |
46036 KB |
Output is correct |
11 |
Correct |
22 ms |
46044 KB |
Output is correct |
12 |
Correct |
22 ms |
46036 KB |
Output is correct |
13 |
Correct |
31 ms |
46096 KB |
Output is correct |
14 |
Correct |
27 ms |
46120 KB |
Output is correct |
15 |
Correct |
28 ms |
46164 KB |
Output is correct |
16 |
Correct |
23 ms |
46164 KB |
Output is correct |
17 |
Correct |
27 ms |
46184 KB |
Output is correct |
18 |
Correct |
25 ms |
46164 KB |
Output is correct |
19 |
Correct |
29 ms |
46152 KB |
Output is correct |
20 |
Correct |
25 ms |
46112 KB |
Output is correct |
21 |
Correct |
26 ms |
46104 KB |
Output is correct |
22 |
Correct |
26 ms |
46196 KB |
Output is correct |
23 |
Correct |
28 ms |
46192 KB |
Output is correct |
24 |
Correct |
31 ms |
46164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
316 ms |
51536 KB |
Output is correct |
2 |
Correct |
283 ms |
51492 KB |
Output is correct |
3 |
Correct |
319 ms |
51812 KB |
Output is correct |
4 |
Correct |
277 ms |
51384 KB |
Output is correct |
5 |
Incorrect |
152 ms |
50764 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
402 ms |
53624 KB |
Output is correct |
2 |
Incorrect |
358 ms |
52164 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
307 ms |
49404 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
45976 KB |
Output is correct |
2 |
Correct |
23 ms |
46028 KB |
Output is correct |
3 |
Correct |
20 ms |
45964 KB |
Output is correct |
4 |
Correct |
21 ms |
46092 KB |
Output is correct |
5 |
Correct |
21 ms |
46036 KB |
Output is correct |
6 |
Correct |
24 ms |
45976 KB |
Output is correct |
7 |
Correct |
22 ms |
45980 KB |
Output is correct |
8 |
Correct |
21 ms |
46044 KB |
Output is correct |
9 |
Correct |
21 ms |
46036 KB |
Output is correct |
10 |
Correct |
21 ms |
46036 KB |
Output is correct |
11 |
Correct |
22 ms |
46044 KB |
Output is correct |
12 |
Correct |
22 ms |
46036 KB |
Output is correct |
13 |
Correct |
31 ms |
46096 KB |
Output is correct |
14 |
Correct |
27 ms |
46120 KB |
Output is correct |
15 |
Correct |
28 ms |
46164 KB |
Output is correct |
16 |
Correct |
23 ms |
46164 KB |
Output is correct |
17 |
Correct |
27 ms |
46184 KB |
Output is correct |
18 |
Correct |
25 ms |
46164 KB |
Output is correct |
19 |
Correct |
29 ms |
46152 KB |
Output is correct |
20 |
Correct |
25 ms |
46112 KB |
Output is correct |
21 |
Correct |
26 ms |
46104 KB |
Output is correct |
22 |
Correct |
26 ms |
46196 KB |
Output is correct |
23 |
Correct |
28 ms |
46192 KB |
Output is correct |
24 |
Correct |
31 ms |
46164 KB |
Output is correct |
25 |
Correct |
316 ms |
51536 KB |
Output is correct |
26 |
Correct |
283 ms |
51492 KB |
Output is correct |
27 |
Correct |
319 ms |
51812 KB |
Output is correct |
28 |
Correct |
277 ms |
51384 KB |
Output is correct |
29 |
Incorrect |
152 ms |
50764 KB |
Output isn't correct |
30 |
Halted |
0 ms |
0 KB |
- |