Submission #1007874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007874		imarn	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	342 ms	40532 KiB

Main

#include<bits/stdc++.h>
//#include "gap.h"
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int mxn=1e5+5;
struct laz{
    int t[4*mxn]{0},lz[4*mxn]{0};
    void build(int i,int l,int r,int x){
        lz[i]=-1e9;
        if(l==r)return void(t[i]=l*x);
        int m=(l+r)>>1;build(2*i,l,m,x);build(2*i+1,m+1,r,x);
        t[i]=max(t[2*i],t[2*i+1]);
    }
    void push(int i,int l,int r){
        t[i]=max(lz[i],t[i]);
        if(l<r)lz[2*i]=max(lz[i],lz[2*i]),lz[2*i+1]=max(lz[i],lz[2*i+1]);
        lz[i]=-1e9;
    }
    void update(int i,int l,int r,int tl,int tr,int v){
        push(i,l,r);
        if(r<tl||l>tr)return;
        if(r<=tr&&l>=tl){
            lz[i]=max(lz[i],v);push(i,l,r);return;
        }int m=(l+r)>>1;update(2*i,l,m,tl,tr,v);update(2*i+1,m+1,r,tl,tr,v);
        t[i]=max(t[2*i],t[2*i+1]);
    }
    int qr(int i,int l,int r,int idx){
        push(i,l,r);
        if(r<idx||l>idx)return -1e9;
        if(l==r)return t[i];
        int m=(l+r)>>1;
        return max(qr(2*i,l,m,idx),qr(2*i+1,m+1,r,idx));
    }
}lsl,lsr;
struct tree{
    int t[2*mxn];
    int qr(int l,int r,int sz,int res=-1e9){
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1)res=max(res,t[l++]);
            if(r&1)res=max(res,t[--r]);
        }return res;
    }
}sl[20],sr[20];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,k,m;cin>>n>>k>>m;
    lsl.build(1,1,n,-1);
    lsr.build(1,1,n,1);
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        if(a<=b)lsr.update(1,1,n,a,min(a+k-1,b-1),b);
        else lsl.update(1,1,n,max(b+1,a-k+1),a,-b);
    }
    for(int i=0;i<n;i++){
        sl[0].t[i+n]=lsl.qr(1,1,n,i+1);
        sr[0].t[i+n]=lsr.qr(1,1,n,i+1);
    }
    for(int i=n-1;i>0;i--)sl[0].t[i]=max(sl[0].t[2*i],sl[0].t[2*i+1]),sr[0].t[i]=max(sr[0].t[2*i],sr[0].t[2*i+1]);
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            int tl=-sl[j-1].qr(i-1,i,n);
            int tr=sr[j-1].qr(i-1,i,n);
            int vl=sl[j-1].qr(tl-1,tr,n);
            int vr=sr[j-1].qr(tl-1,tr,n);
            sl[j].t[i+n-1]=vl;sr[j].t[i+n-1]=vr;
        }for(int i=n-1;i>0;i--)sl[j].t[i]=max(sl[j].t[2*i],sl[j].t[2*i+1]),sr[j].t[i]=max(sr[j].t[2*i],sr[j].t[2*i+1]);
    }int q;cin>>q;
    while(q--){
        int u,v;cin>>u>>v;
        int l=u,r=u;int ans=0;
        int tl=-sl[19].qr(l-1,r,n);
        int tr=sr[19].qr(l-1,r,n);
        if(tl>v||tr<v){cout<<-1<<'\n';continue;}
        for(int i=19;i>=0;i--){
            int tl=-sl[i].qr(l-1,r,n);
            int tr=sr[i].qr(l-1,r,n);
            if(tl>v||tr<v)ans|=(1<<i),l=tl,r=tr;
        }cout<<ans+1<<'\n';
    }
}

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