Submission #1028302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028302		snpmrnhlol	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	404 ms	32704 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int Q = 5e4;
const int logN = 20;
const int inf = 2e9;
vector <int> op[N + 1];
multiset <int> s;
int l[N][logN],r[N][logN];
int segl[N*2],segr[N*2];
int q1[Q],q2[Q];
int ql1[Q],qr1[Q];
int ans[Q];
int n,k,m,q;
void build(int id){
    for(int i = 2*n - 1;i > 0;i--){
        if(i >= n){
            segl[i] = l[i - n][id];
            segr[i] = r[i - n][id];
        }else{
            segl[i] = min(segl[i*2],segl[i*2 + 1]);
            segr[i] = max(segr[i*2],segr[i*2 + 1]);
        }
    }
}
pair<int,int> query(int ql, int qr){
    pair<int,int> x = {inf,-inf};
    qr++;
    for(ql+=n,qr+=n;ql < qr;ql/=2,qr/=2){
        if(ql&1){
            x.first = min(x.first,segl[ql]);
            x.second = max(x.second,segr[ql]);
            ql++;
        }
        if(qr&1){
            qr--;
            x.first = min(x.first,segl[qr]);
            x.second = max(x.second,segr[qr]);
        }
    }
    return x;
}
int main(){
    cin>>n>>k;
    cin>>m;
    for(int i = 0;i < m;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        if(a < b){
            op[a].push_back(b + 1);
            op[min(a + k,b)].push_back(-(b + 1));
        }else{
            op[max(a - k + 1,b + 1)].push_back(b + 1);
            op[a + 1].push_back(-(b + 1));
        }
    }
    for(int i = 0;i < n;i++){
        for(auto j:op[i]){
            if(j > 0){
                s.insert(j - 1);
            }else{
                s.erase(s.find(-j - 1));
            }
        }
        s.insert(i);
        l[i][0] = *s.begin();
        r[i][0] = *s.rbegin();
        s.erase(s.find(i));
    }
    for(int j = 1;j < logN;j++){
        ///nlog^2n im crying and shaking rn
        build(j - 1);
        for(int i = 0;i < n;i++){
            auto x = query(l[i][j - 1],r[i][j - 1]);
            l[i][j] = x.first;
            r[i][j] = x.second;
        }
    }
    ///PBS lesgooooooooo
    cin>>q;
    for(int i = 0;i < q;i++){
        cin>>q1[i]>>q2[i];
        q1[i]--;
        q2[i]--;
        ql1[i] = qr1[i] = q1[i];
        ans[i] = 1;
    }
    for(int j = logN - 1;j >= 0;j--){
        build(j);
        for(int i = 0;i < q;i++){
            auto x = query(ql1[i],qr1[i]);
            if(!(x.first <= q2[i] && q2[i] <= x.second)){
                ql1[i] = x.first;
                qr1[i] = x.second;
                ans[i]+=(1<<j);
            }
        }
    }
    for(int i = 0;i < q;i++){
        if(ans[i] == (1<<logN))ans[i] = -1;
        cout<<ans[i]<<'\n';
    }
    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