Submission #1007872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007872		imarn	Railway Trip 2 (JOI22_ho_t4)	C++14	52 / 100	2080 ms	94948 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 tl,int tr){
        push(i,l,r);
        if(r<tl||l>tr)return -1e9;
        if(r<=tr&&l>=tl)return t[i];
        int m=(l+r)>>1;
        return max(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
    }
}sl[20],sr[20];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,k,m;cin>>n>>k>>m;
    sl[0].build(1,1,n,-1);
    sr[0].build(1,1,n,1);
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        if(a<=b)sr[0].update(1,1,n,a,min(a+k-1,b-1),b);
        else sl[0].update(1,1,n,max(b+1,a-k+1),a,-b);
    }
    for(int j=1;j<20;j++){
        sl[j].build(1,1,n,-1);
        sr[j].build(1,1,n,-1);
        for(int i=1;i<=n;i++){
            int tl=-sl[j-1].qr(1,1,n,i,i);
            int tr=sr[j-1].qr(1,1,n,i,i);
            int vl=sl[j-1].qr(1,1,n,tl,tr);
            int vr=sr[j-1].qr(1,1,n,tl,tr);
            sl[j].update(1,1,n,i,i,vl);sr[j].update(1,1,n,i,i,vr);
        }
    }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(1,1,n,l,r);
        int tr=sr[19].qr(1,1,n,l,r);
        if(tl>v||tr<v){cout<<-1<<'\n';continue;}
        for(int i=19;i>=0;i--){
            int tl=-sl[i].qr(1,1,n,l,r);
            int tr=sr[i].qr(1,1,n,l,r);
            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: 0 / 35
• Subtask 6: 0 / 13