Submission #1244612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244612		nasjes	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	1175 ms	131772 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#include "unordered_set"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;

const ll dim = 4e5+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e18 + 177;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n,  m, x, y, k, q;

pll t[24][4*dim];
vector<pll> ev[dim];
pll road[dim];
ll gol[dim], gor[dim];
pll ask(ll v, ll tl, ll tr, ll l, ll r, ll id){
    if(tl>r || tr<l)return{inf, -inf};
    if(l<=tl && tr<=r)return t[id][v];
    ll tm=(tl+tr)/2;
    pll cur1= ask(2*v, tl, tm, l, r, id);
    pll cur2= ask(2*v+1, tm+1, tr, l, r, id);
    return {min(cur1.fi, cur2.fi), max(cur1.se, cur2.se)};


}
void build(ll v, ll tl, ll tr, ll id){
    if(tl==tr){
        if(id==0){
            t[id][v]={gol[tl], gor[tl]};
            //cout<<tl<<" "<<tr<<"     "<<t[id][v].fi<<" "<<t[id][v].se<<endl;
        }
        else{
            pll nw=ask(1, 1, n, tl, tl, id-1);
            nw=ask(1, 1, n, nw.fi, nw.se, id-1);
            t[id][v]=nw;
        }
        return;
    }
    ll tm=(tl+tr)/2;
    build(2*v, tl, tm, id);
    build(2*v+1, tm+1, tr, id);
    t[id][v]={min(t[id][2*v].fi, t[id][2*v+1].fi), max(t[id][2*v].se, t[id][2*v+1].se)};
    if(id==0){
       // cout<<tl<<" "<<tr<<"     "<<t[id][v].fi<<" "<<t[id][v].se<<endl;
    }
}
ll qu(ll u, ll v){
    pll mx=ask(1, 1, n, u, u, 22);
    //cout<<mx.fi<<" "<<mx.se<<endl;
    if(!(mx.fi<=v && v<=mx.se))return -1;
    ll jumpl=u;
    ll jumpr=u;
    ll res=0;
    for(int i=21; i>=0; i--){
        pll cur=ask(1,1, n, jumpl, jumpr, i);
     //   cout<<i<<" "<<cur.fi<<" "<<cur.se<<endl;
        if(!(cur.fi<=v && v<=cur.se)){
            res+=(1ll<<i);
            jumpl=cur.fi;
            jumpr=cur.se;
        }
    }
    return res+1;
}

int main() {
    cin>>n>>k>>m;
    ll u, v;
    vector<ll> lt;
    vector<ll> rt;
    for(int i=1; i<=m; i++){
        cin>>u>>v;
        if(u>v)lt.pb(i);
        else rt.pb(i);
        if(u>v)swap(u, v);
        road[i].fi=u; road[i].se=v;
    }
    for(auto id:rt){
        pll el=road[id];
        ll end=min(n+1, el.fi+k);
        ev[el.fi].pb({1, id});
        ev[end].pb({-1, id});
    }
    for(int i=1; i<=n; i++){
        gol[i]=i;
        gor[i]=i;
    }
    set<pll> op;
    for(int i=1; i<=n; i++){
        for(auto el: ev[i]){
            if(el.fi==-1)op.erase({road[el.se].se, el.se});
            else op.insert({road[el.se].se, el.se});
        }
        ev[i].clear();
        if(op.size()>0)gor[i]=max(gor[i], (*op.rbegin()).fi);
        else gor[i]=i;//or -inf
    }
    for(int i=0; i<=n+1; i++)ev[i].clear();
    op.clear();
    for(auto id:lt){
        pll el=road[id];
        ll end=max(0ll, el.se-k);
        ev[el.se].pb({1, id});
        ev[end].pb({-1, id});
    }
    for(int i=n; i>=1; i--){
        for(auto el: ev[i]){
            if(el.fi==-1)op.erase({road[el.se].fi, el.se});
            else op.insert({road[el.se].fi, el.se});
        }
        if(op.size()>0)gol[i]=min(gol[i], (*op.begin()).fi);
        else gol[i]=i; // or inf
    }
    for(int i=0; i<=22; i++){
        build(1, 1, n, i);
    }
    cin>>q;
   // cout<<" --" <<endl;
    while(q--){
        cin>>u>>v;
        cout<<qu(u, v)<<endl;
    }
    return 0;
}

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