Submission #745251

#	Time	Username	Problem	Language	Result	Execution time	Memory
745251		1075508020060209tc	Railway Trip 2 (JOI22_ho_t4)	C++14	35 / 100	537 ms	258272 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];


void build(int id){
for(int i=1;i<=n;i++){
    rmq[id][0][i]=jmp[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))]);
    }
}
}
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]);
}


signed main(){
cin>>n>>K;
cin>>m;
for(int i=1;i<=m;i++){
    int a;int b;
    cin>>a>>b;
    rts[a].push_back({min(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();
    }
}
//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,j,jmp[i-1][j]);
    }
   // cout<<i<<endl;
}

cin>>Q;
while(Q--){
    int st;int en;
    cin>>st>>en;
    int nw=st;
    int ans=0;
    for(int i=17;i>=0;i--){
        int nxt=qmx(i,st,nw);
        if(nxt<en){
            nw=nxt;
            ans+=(1<<i);
        }
    }
   // cout<<nw<<" "<<qmx(0,st,nw)<<" "<<jmp[0][nw]<<endl;
    if(qmx(0,st,nw)<en){
        cout<<-1<<endl;
    }else{
        cout<<ans+1<<endl;
    }


}





}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:43: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]
   43 |     for(int j=0;j<rts[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