| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 745280 | 1075508020060209tc | Railway Trip 2 (JOI22_ho_t4) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;int K;
int m;
int Q;
vector<pair<int,int>>rts[100005];
int rmq[19][19][100005];
int jmp[19][100005];
vector<pair<int,int>>rrts[100005];
int rrmq[19][19][100005];
int rjmp[19][100005];
void build(int id){
for(int i=1;i<=n;i++){
rmq[id][0][i]=jmp[id][i];
rrmq[id][0][i]=rjmp[id][i];
}
for(int i=1;i<=18;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
rmq[id][i][j]=max(rmq[id][i-1][j],rmq[id][i-1][j+(1<<(i-1))]);
rrmq[id][i][j]=min(rrmq[id][i-1][j],rrmq[id][i-1][j+(1<<(i-1))]);
}
}
}
int qmx(int id,int l,int r){
int len=r-l+1;
int lg=__lg(len);
return max(rmq[id][lg][l],rmq[id][lg][r-(1<<lg)+1]);
}
int qmn(int id,int l,int r){
int len=r-l+1;
int lg=__lg(len);
return min(rrmq[id][lg][l],rrmq[id][lg][r-(1<<lg)+1]);
}
signed main(){
cin>>n>>K;
cin>>m;
for(int i=1;i<=m;i++){
int a;int b;
cin>>a>>b;
if(a<b){
rts[a].push_back({min(b,a+K-1),b});
}
else{
rrts[a].push_back({max(b,a-K+1),b});
}
}
multiset<int>mst;
multiset<pair<int,int>>mst2;
for(int i=1;i<=n;i++){
for(int j=0;j<rts[i].size();j++){
mst.insert(rts[i][j].second);
mst2.insert({rts[i][j].first,rts[i][j].second});
}
while(mst2.size()&&(*mst2.begin()).first<i){
mst.erase(mst.find((*mst2.begin()).second));
mst2.erase(mst2.begin());
}
jmp[0][i]=i;
if(mst.size()){
jmp[0][i]=*mst.rbegin();
}
}
mst.clear();
mst2.clear();
for(int i=n;i>=1;i--){
for(int j=0;j<rrts[i].size();j++){
mst.insert(rrts[i][j].second);
mst2.insert({rrts[i][j].first,rrts[i][j].second});
}
while(mst2.size()&&((*mst2.rbegin()).first)>i){
mst.erase(mst.find((*mst2.rbegin()).second));
mst2.erase(mst2.rbegin());
}
rjmp[0][i]=i;
if(mst.size()){
rjmp[0][i]=*mst.begin();
}
}
/*
for(int i=1;i<=n;i++){
cout<<rjmp[0][i]<<" ";
}cout<<endl;*/
//cout<<"hehe";
for(int i=1;i<=18;i++){
build(i-1);
for(int j=1;j<=n;j++){
jmp[i][j]=qmx(i-1,rjmp[i-1][j],jmp[i-1][j]);
rjmp[i][j]=qmn(i-1,rjmp[i-1][j],jmp[i-1][j]);
}
// cout<<i<<endl;
}
cin>>Q;
while(Q--){
int st;int en;
cin>>st>>en;
if(st<en){
int nwl=st;
int nwr=st;
int ans=0;
for(int i=17;i>=0;i--){
int nxtr=qmx(i,nwl,nwr);
if(nxtr<en){
nwl=qmn(i,nwl,nwr);
nwr=nxtr;
ans+=(1<<i);
}
}
// cout<<nw<<" "<<qmx(0,st,nw)<<" "<<jmp[0][nw]<<endl;
if(qmx(0,nwl,nwr)<en){
cout<<-1<<endl;
}else{
cout<<ans+1<<endl;
}
continue;
}
int nwl=st;
int nwr=st;
int ans=0;
for(int i=17;i>=0;i--){
int nxtl=qmn(i,nwl,nwr);
if(nxtl>en){
nwr=qmx(i,nwl,nwr);
nwl=nxtl;
ans+=(1<<i);
}
}
// cout<<nw<<" "<<qmx(0,st,nw)<<" "<<jmp[0][nw]<<endl;
if(qmn(0,nwl,nwr)>en){
cout<<-1<<endl;
}else{
cout<<ans+1<<endl;
}
}
}