#include<bits/stdc++.h>
#define F first
#define S second
#define lc id*2+1
#define rc id*2+2
#define MP make_pair
using namespace std;
const int maxn=1e6;
pair<int,int> operator+(pair<int,int> a,pair<int,int> b){
return MP(min(a.F,b.F),max(a.S,b.S));
}
pair<int,int> iit={maxn,0};
struct node{
pair<int,int> val,tag;
};
int fl[100010][20],fr[100010][20],n,m,k;
node tri[400010];
void push(int l,int r,int id){
if(tri[id].tag!=iit){
tri[id].val=tri[id].tag+tri[id].val;
if(l!=r){
tri[lc].tag=tri[lc].tag+tri[id].tag;
tri[rc].tag=tri[rc].tag+tri[id].tag;
}
tri[id].tag=iit;
}
return;
}
void pull(int l,int r,int id){
push(l,r,id);
if(l!=r){
int m=(l+r)>>1;
push(l,m,lc);
push(m+1,r,rc);
tri[id].val=tri[lc].val+tri[rc].val;
}
return;
}
void build(int l,int r,int id,int i){
tri[id].tag=iit;
if(l==r){
tri[id].val={fl[l][i],fr[l][i]};
return;
}
int m=(l+r)>>1;
build(l,m,lc,i);
build(m+1,r,rc,i);
pull(l,r,id);
}
void modify(int l,int r,int L,int R,int id,int x){
pull(l,r,id);
if(l==L&&r==R){
tri[id].tag=tri[id].tag+MP(x,x);
return;
}
int m=(l+r)>>1;
if(R<=m){
modify(l,m,L,R,lc,x);
}else if(L>m){
modify(m+1,r,L,R,rc,x);
}else{
modify(l,m,L,m,lc,x);
modify(m+1,r,m+1,R,rc,x);
}
pull(l,r,id);
return;
}
pair<int,int> query(int l,int r,int L,int R,int id){
pull(l,r,id);
if(l==L&&r==R){
return tri[id].val;
}
int m=(l+r)>>1;
if(R<=m){
return query(l,m,L,R,lc);
}else if(L>m){
return query(m+1,r,L,R,rc);
}else{
return query(l,m,L,m,lc)+query(m+1,r,m+1,R,rc);
}
}
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
cin>>n>>k>>m;
for(int j=1;j<=n;j++){
fl[j][0]=j;
fr[j][0]=j;
}
build(1,n,0,0);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
if(a<b){
modify(1,n,a,min(a+k-1,b),0,b);
}else{
modify(1,n,max(a-k+1,b),a,0,b);
}
}
for(int i=1;i<=18;i++){
for(int j=1;j<=n;j++){
auto now=query(1,n,fl[j][i-1],fr[j][i-1],0);
fl[j][i]=now.F;
fr[j][i]=now.S;
}
build(1,n,0,i);
}
int q;
cin>>q;
for(int i=0;i<q;i++){
int s,t,ans=0;
cin>>s>>t;
if(s<t){
if(fr[s][18]<t){
cout<<"-1\n";
continue;
}
for(int j=18;j>0;j--){
if(fr[s][j]<t){
ans+=1<<(j-1);
s=fr[s][j];
}
}
cout<<ans+1<<"\n";
}else{
if(fl[s][18]>t){
cout<<"-1\n";
continue;
}
for(int j=18;j>0;j--){
if(fl[s][j]>t){
ans+=1<<(j-1);
s=fl[s][j];
}
}
cout<<ans+1<<"\n";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
811 ms |
22608 KB |
Output is correct |
2 |
Correct |
734 ms |
22364 KB |
Output is correct |
3 |
Correct |
889 ms |
22608 KB |
Output is correct |
4 |
Correct |
689 ms |
22360 KB |
Output is correct |
5 |
Correct |
351 ms |
22364 KB |
Output is correct |
6 |
Correct |
737 ms |
22364 KB |
Output is correct |
7 |
Correct |
236 ms |
22360 KB |
Output is correct |
8 |
Correct |
214 ms |
22108 KB |
Output is correct |
9 |
Correct |
231 ms |
22608 KB |
Output is correct |
10 |
Correct |
823 ms |
22360 KB |
Output is correct |
11 |
Correct |
650 ms |
22364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
689 ms |
22608 KB |
Output is correct |
2 |
Correct |
994 ms |
22364 KB |
Output is correct |
3 |
Correct |
857 ms |
22604 KB |
Output is correct |
4 |
Correct |
259 ms |
22360 KB |
Output is correct |
5 |
Correct |
396 ms |
22276 KB |
Output is correct |
6 |
Correct |
428 ms |
22364 KB |
Output is correct |
7 |
Correct |
937 ms |
22360 KB |
Output is correct |
8 |
Correct |
696 ms |
22364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
891 ms |
22600 KB |
Output is correct |
2 |
Correct |
777 ms |
22612 KB |
Output is correct |
3 |
Correct |
774 ms |
22608 KB |
Output is correct |
4 |
Correct |
816 ms |
22616 KB |
Output is correct |
5 |
Correct |
609 ms |
22452 KB |
Output is correct |
6 |
Correct |
903 ms |
22364 KB |
Output is correct |
7 |
Correct |
645 ms |
22364 KB |
Output is correct |
8 |
Correct |
2 ms |
4444 KB |
Output is correct |
9 |
Correct |
11 ms |
6492 KB |
Output is correct |
10 |
Correct |
864 ms |
22352 KB |
Output is correct |
11 |
Correct |
849 ms |
22364 KB |
Output is correct |
12 |
Correct |
858 ms |
22276 KB |
Output is correct |
13 |
Correct |
837 ms |
22376 KB |
Output is correct |
14 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |