Submission #745278

#	Time	Username	Problem	Language	Result	Execution time	Memory
745278		1075508020060209tc	Railway Trip 2 (JOI22_ho_t4)	C++14	35 / 100	737 ms	494760 KiB

Main

#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.begin()).second));
        mst2.erase(mst2.begin());
    }
    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;
    }
}





}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:58:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int j=0;j<rts[i].size();j++){
      |                 ~^~~~~~~~~~~~~~
Main.cpp:74:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int j=0;j<rrts[i].size();j++){
      |                 ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 35 / 35
• Subtask 6: 0 / 13