Submission #959421

#	Time	Username	Problem	Language	Result	Execution time	Memory
959421		happy_node	Railway Trip 2 (JOI22_ho_t4)	C++17	0 / 100	396 ms	61692 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=2e5+5, MK=18;

int N,K,M,Q;

struct segtree {
        pair<int,int> t[4 * MX];
 
        void update(int v, int l, int r, int pos, pair<int,int> val) {
                if(l > pos || r < pos) return;
                if(l == r) {
                        t[v] = val;
                        return;
                }
                int mid = (l + r) >> 1;
                update(v * 2 + 0, l, mid + 0, pos, val);
                update(v * 2 + 1, mid + 1, r, pos, val);
                t[v] = max(t[v * 2 + 0], t[v * 2 + 1]);
        }
 
        pair<int,int> query(int v, int l, int r, int ql, int qr) {
                if(ql > r || qr < l) return make_pair(0,0);
                if(ql <= l && qr >= r) return t[v];
                int mid = (l + r) >> 1;
                return max(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
        }

        void reset() {
                for(int i=0;i<4*MX;i++)
                        t[i]=make_pair(0,0);
        }
} st;

int L[MX], R[MX], dep[MX], S[MX], T[MX];
vector<int> adj[MX];

int up[MX][MK];

void dfs(int v) {
        for(int k=1;k<MK;k++) {
                up[v][k]=up[up[v][k-1]][k-1];
        }
        for(auto u:adj[v]) {
                dep[u]=dep[v]+1;
                up[u][0]=v;
                dfs(u);
        }
}

set<pair<int,int>> pends[MX];

int find(int v, int r) {
        for(int k=MK-1;k>=0;k--) {
                if(up[v][k]!=0 && R[up[v][k]]<r) {
                        v=up[v][k];
                }
        }
        return up[v][0];
}

int main() {
        cin.tie(0); ios_base::sync_with_stdio(0);

        for(int i=0;i<MX;i++) pends[i].insert(make_pair(0,0));

        cin>>N>>K>>M;

        vector<array<int,3>> v;

        for(int i=1;i<=M;i++) {
                int a,b;
                cin>>a>>b;
                L[i]=a;
                R[i]=b;
                v.push_back({a,0,i});
                v.push_back({min(a+K-1,b-1),1,i});
                v.push_back({b,2,i});
        }

        sort(v.begin(),v.end());

        for(auto [p,t,id]:v) {
                if(t==0) {
                        st.update(1,1,N,p,make_pair(R[id],id));
                } else if(t==1) {
                        st.update(1,1,N,p,make_pair(R[id],id));
                } else {
                        int nxt=st.query(1,1,N,L[id],R[id]).second;
                        if(nxt!=0 && nxt!=id) {
                                adj[nxt].push_back(id);
                        }
                }
        }

        dfs(v.back()[2]);

        st.reset();

        v.clear();
        for(int i=1;i<=N;i++) {
                v.push_back({i,1,-1});
        }
        for(int i=1;i<=M;i++) {
                v.push_back({L[i],0,i});
                v.push_back({min(L[i]+K-1,R[i]-1),2,i});
        }

        sort(v.begin(),v.end());

        multiset<int> mx,mn;

        for(auto [p,t,id]:v) {
                if(t==0) {
                        pends[p].insert(make_pair(R[id],id));
                        st.update(1,1,N,p,*pends[p].rbegin());
                } else if(t==1) { // query
                        S[p]=st.query(1,1,N,1,p).second;
                } else {
                        pends[L[id]].erase(make_pair(R[id],id));
                        st.update(1,1,N,L[id],*pends[L[id]].rbegin());
                }
        }

        cin>>Q;

        for(int i=0;i<Q;i++) {
                int s,t;
                cin>>s>>t;

                if(S[s]==0) {
                        cout<<-1<<'\n';
                        continue;
                }

                if(R[S[s]]>=t) {
                        cout<<1<<'\n';
                        continue;
                }

                int T=find(S[s],t);
                if(t<L[T]) {
                        cout<<-1<<'\n';
                        continue;
                }

                cout<<dep[S[s]]-dep[T]+1<<'\n';
        }       
}

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