Submission #1225217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225217		TadijaSebez	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	1183 ms	79452 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int inf=1e9+7;

const int N=100050;
const int L=18;
int mnl[N][L],mxr[N][L];
vector<int> ql[N],qr[N];

const int M=2*N*(L+1);
int root[L],ls[M],rs[M],tsz;
pair<int,int> val[M];

pair<int,int> operator + (pair<int,int> a,pair<int,int> b){
    return {min(a.first,b.first),max(a.second,b.second)};
}

void Build(int&c,int ss,int se,int lvl){
    c=++tsz;
    if(ss==se){
        val[c]={mnl[ss][lvl],mxr[ss][lvl]};
        return;
    }
    int mid=ss+se>>1;
    Build(ls[c],ss,mid,lvl);
    Build(rs[c],mid+1,se,lvl);
    val[c]=val[ls[c]]+val[rs[c]];
}
pair<int,int> Get(int c,int ss,int se,int qs,int qe){
    if(qs>qe||qs>se||ss>qe)return {inf,-inf};
    if(qs<=ss&&qe>=se)return val[c];
    int mid=ss+se>>1;
    return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
int main(){
    int n,k,m;
    scanf("%i %i %i",&n,&k,&m);
    for(int i=1;i<=n;i++){
        mnl[i][0]=i;
        mxr[i][0]=i;
    }
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%i %i",&a,&b);
        if(a<b)mxr[a][0]=max(mxr[a][0],b);
        else mnl[a][0]=min(mnl[a][0],b);
    }
    Build(root[0],1,n,0);
    for(int i=1;i<=n;i++){
        mnl[i][0]=Get(root[0],1,n,i,i+k-1).first;
        mxr[i][0]=Get(root[0],1,n,i-k+1,i).second;
    }
    Build(root[0],1,n,0);
    for(int j=1;j<L;j++){
        for(int i=1;i<=n;i++){
            tie(mnl[i][j],mxr[i][j])=Get(root[j-1],1,n,mnl[i][j-1],mxr[i][j-1]);
        }
        Build(root[j],1,n,j);
    }
    int q;
    scanf("%i",&q);
    while(q--){
        int s,t;
        scanf("%i %i",&s,&t);
        if(mnl[s][L-1]>t || mxr[s][L-1]<t){
            printf("-1\n");
        }else{
            int l=s,r=s,ans=0;
            for(int i=L-1;i>=0;i--){
                auto now=Get(root[i],1,n,l,r);
                if(now.first>t || now.second<t){
                    ans+=1<<i;
                    tie(l,r)=now;
                }
            }
            printf("%i\n",ans+1);
        }
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%i %i %i",&n,&k,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%i %i",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
Main.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%i",&q);
      |     ~~~~~^~~~~~~~~
Main.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%i %i",&s,&t);
      |         ~~~~~^~~~~~~~~~~~~~~

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