Submission #1028276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028276		snpmrnhlol	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	528 ms	33108 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int Q = 5e4;
const int logN = 20;
vector <int> op[N + 1];
multiset <int> s;
int l[N][logN],r[N][logN];
int segl[N*4],segr[N*4];
int q1[Q],q2[Q];
int ql1[Q],qr1[Q];
int ans[Q];
int n,k,m,q;
void build(int l2, int r2, int id, int node = 1){
    if(l2 == r2){
        segl[node] = l[l2][id];
        segr[node] = r[l2][id];
    }else{
        int mij = (l2 + r2)/2;
        build(l2, mij, id, node*2);
        build(mij + 1, r2, id, node*2 + 1);
        segl[node] = min(segl[node*2],segl[node*2 + 1]);
        segr[node] = max(segr[node*2],segr[node*2 + 1]);
    }
}
pair<int,int> query(int ql, int qr, int l2 = 0, int r2 = n - 1, int node = 1){
    if(ql <= l2 && r2 <= qr){
        return {segl[node],segr[node]};
    }else{
        int mij = (l2 + r2)/2;
        if(qr <= mij){
            return query(ql, qr, l2, mij, node*2);
        }else if(mij + 1 <= ql){
            return query(ql, qr, mij + 1, r2, node*2 + 1);
        }else{
            auto x = query(ql, qr, l2, mij, node*2);
            auto y = query(ql, qr, mij + 1, r2, node*2 + 1);
            return {min(x.first,y.first),max(x.second,y.second)};
        }
    }
}
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(0, n - 1, 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(0,n - 1,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