Submission #528190

#	Time	Username	Problem	Language	Result	Execution time	Memory
528190		doowey	Railway Trip 2 (JOI22_ho_t4)	C++14	16 / 100	556 ms	71720 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 1;
const int LOG = 18;
int L[LOG][N];
int R[LOG][N];
multiset<int> add[N];
multiset<int> del[N];

int A[N];
int B[N];

pii segt[LOG][N * 4 + 512];

void build(int dep, int node, int lef, int rig){
    if(lef == rig){
        segt[dep][node] = mp(L[dep][lef], R[dep][rig]);
        return;
    }
    int mid = (lef + rig) / 2;
    build(dep, node * 2, lef, mid);
    build(dep, node * 2 + 1, mid + 1, rig);
    segt[dep][node].fi = min(segt[dep][node*2].fi, segt[dep][node*2+1].fi);
    segt[dep][node].se = max(segt[dep][node*2].se, segt[dep][node*2+1].se);
}

pii get(int dep, int node, int cl, int cr, int tl, int tr){
    if(cr < tl || cl > tr){
        return mp((int)1e9,-1);
    }
    if(cl >= tl && cr <= tr){
        return segt[dep][node];
    }
    int mid = (cl + cr) / 2;
    pii A = get(dep, node * 2, cl, mid, tl, tr);
    pii B = get(dep, node * 2 + 1, mid + 1, cr, tl, tr);
    return mp(min(A.fi, B.fi), max(A.se, B.se));
}


int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n, k;
    cin >> n >> k;
    int m;
    cin >> m;
    int seg;
    for(int id = 1; id <= m ;id ++ ){
        cin >> A[id] >> B[id];
        if(A[id] < B[id]){
            seg = min(B[id], A[id] + k - 1);
            add[A[id]].insert(B[id]);
            del[seg + 1].insert(B[id]);
        }
        else{
            seg = max(A[id] - k + 1, B[id]);
            add[seg].insert(B[id]);
            del[A[id] + 1].insert(B[id]);
        }
    }
    multiset<int> pp;
    int low;
    for(int iq = 1; iq <= n; iq ++ ){
        for(auto x : add[iq]){
            pp.insert(x);
        }
        for(auto x : del[iq]){
            pp.erase(pp.find(x));
        }
        L[0][iq] = R[0][iq] = iq;
        if(!pp.empty()){
            auto it = pp.begin();
            L[0][iq] = min(L[0][iq], *it);
            it = pp.end();
            it -- ;
            R[0][iq] = max(R[0][iq], *it);
        }
    }
    pii F;
    for(int c = 1; c < LOG; c ++ ){
        build(c - 1, 1, 1, n);
        for(int iq = 1; iq <= n; iq ++ ){
            F = get(c - 1, 1, 1, n, L[c-1][iq], R[c-1][iq]);
            L[c][iq] = F.fi;
            R[c][iq] = F.se;
        }
    }
    build(LOG - 1, 1, 1, n);
    int q;
    cin >> q;
    int s, t;
    int lef, rig;
    int dep;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> s >> t;
        lef = rig = s;
        dep = 0;
        for(int lg = LOG - 1; lg >= 0 ; lg -- ){
            F = get(lg, 1, 1, n, lef, rig);
            if(t < F.fi || t > F.se){
                lef = F.fi;
                rig = F.se;
                dep += (1 << lg);
            }
        }
        F = get(0, 1, 1, n, lef, rig);
        if(F.fi <= t && t <= F.se){
            cout << dep + 1 << "\n";
        }
        else{
            cout << -1 << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:73:9: warning: unused variable 'low' [-Wunused-variable]
   73 |     int low;
      |         ^~~

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