//challenge: 100
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define x first
#define y second
//#define endl '\n'
int n,k,m;
const int INF=1e9;
vector<vector<int>> dp1,dp2;
struct segmax{
int l,r,m;
int val=-INF;
int lz=-INF;
segmax *lc,*rc;
segmax(int l1,int r1){
l=l1,r=r1;
m=(l+r)>>1;
if(r-l==1){
return;
}
lc=new segmax(l,m);
rc=new segmax(m,r);
}
int rv(){
if(lz==-INF){
return val;
}
return max(val,lz);
}
void pull(){
val=max({lc->rv(),rc->rv(),val});
}
void push(){
if(lz!=-INF){
lc->lz=max(lc->lz,lz);
rc->lz=max(rc->lz,lz);
lz=-INF;
}
pull();
}
void add(int a,int b,int x){
if(a<=l&&b>=r){
lz=max(lz,x);
return;
}
push();
if(a<m){
lc->add(a,b,x);
}
if(b>m){
rc->add(a,b,x);
}
pull();
}
int query(int a,int b){
if(a<=l&&b>=r){
return rv();
}
push();
int ans=-INF;
if(a<m){
ans=max(ans,lc->query(a,b));
}
if(b>m){
ans=max(ans,rc->query(a,b));
}
pull();
return ans;
}
};
struct segmin{
int l,r,m;
int val=INF;
int lz=INF;
segmin *lc,*rc;
segmin(int l1,int r1){
l=l1,r=r1;
m=(l+r)>>1;
if(r-l==1){
return;
}
lc=new segmin(l,m);
rc=new segmin(m,r);
}
int rv(){
if(lz==INF){
return val;
}
return min(val,lz);
}
void pull(){
val=min({lc->rv(),rc->rv(),val});
}
void push(){
if(lz!=INF){
lc->lz=min(lc->lz,lz);
rc->lz=min(rc->lz,lz);
lz=INF;
}
pull();
}
void add(int a,int b,int x){
if(a<=l&&b>=r){
lz=min(lz,x);
return;
}
push();
if(a<m){
lc->add(a,b,x);
}
if(b>m){
rc->add(a,b,x);
}
pull();
}
int query(int a,int b){
if(a<=l&&b>=r){
return rv();
}
push();
int ans=INF;
if(a<m){
ans=min(ans,lc->query(a,b));
}
if(b>m){
ans=min(ans,rc->query(a,b));
}
pull();
return ans;
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k>>m;
dp1.resize(20,vector<int>(n));
dp2.resize(20,vector<int>(n));
segmax *rt=new segmax(0,n);
segmin *rt1=new segmin(0,n);
for(int i=0;i<m;i++){
int a,b;cin>>a>>b;
a--;b--;
if(a<b){
int c=min(b,a+k-1);
rt->add(a,c+1,b);
}
else{
int c=max(b,a-k+1);
rt1->add(c,a+1,b);
}
}
for(int i=0;i<n;i++){
rt->add(i,i+1,i);
rt1->add(i,i+1,i);
}
for(int i=0;i<n;i++){
dp1[0][i]=rt1->query(i,i+1);
dp2[0][i]=rt->query(i,i+1);
//cout<<dp1[0][i]<<' '<<dp2[0][i]<<endl;
}
for(int i=1;i<20;i++){
segmax *mx=new segmax(0,n);
segmin *mn=new segmin(0,n);
for(int j=0;j<n;j++){
mx->add(j,j+1,dp2[i-1][j]);
mn->add(j,j+1,dp1[i-1][j]);
}
for(int j=0;j<n;j++){
dp1[i][j]=mn->query(dp1[i-1][j],dp2[i-1][j]+1);
dp2[i][j]=mx->query(dp1[i-1][j],dp2[i-1][j]+1);
}
}
/*for(int i=0;i<20;i++){
for(int j=0;j<n;j++){
cout<<dp1[i][j]<<' ';
}
cout<<endl;
}*/
int q;cin>>q;
for(int i=0;i<q;i++){
int a,b;cin>>a>>b;
a--;b--;
if(a<b){
if(dp2[19][a]<b){
cout<<-1<<endl;
}
else{
int ans=0;
for(int j=19;j>=0;j--){
if(dp2[j][a]<b){
ans+=(1<<j);
a=dp2[j][a];
}
}
cout<<ans+1<<endl;
}
}
else{
if(dp1[19][a]>b){
cout<<-1<<endl;
}
else{
int ans=0;
for(int j=19;j>=0;j--){
if(dp1[j][a]>b){
ans+=(1<<j);
a=dp1[j][a];
}
}
cout<<ans+1<<endl;
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2001 ms |
391664 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1893 ms |
391832 KB |
Output is correct |
| 2 |
Correct |
1980 ms |
394692 KB |
Output is correct |
| 3 |
Execution timed out |
2095 ms |
393112 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1978 ms |
391776 KB |
Output is correct |
| 2 |
Execution timed out |
2054 ms |
393032 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
