Submission #959626

#	Time	Username	Problem	Language	Result	Execution time	Memory
959626		happy_node	Railway Trip 2 (JOI22_ho_t4)	C++17	60 / 100	679 ms	71356 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 set(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;
                set(v * 2 + 0, l, mid + 0, pos, val);
                set(v * 2 + 1, mid + 1, r, pos, val);
                t[v] = max(t[v * 2 + 0], t[v * 2 + 1]);
        }
 
        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] = max(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], nxt[MX];
vector<int> adj[MX];

int up[MX][MK];
bool root[MX];

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 ans[MX];

void work() {
        for(int i=0;i<MX;i++) {
                dep[i]=0;
                nxt[i]=0;
                pends[i].clear();
                pends[i].insert(make_pair(0,0));
                adj[i].clear();
                root[i]=1;
                for(int j=0;j<MK;j++) {
                        up[i][j]=0;
                }
        }
        st.reset();
        
        vector<array<int,3>> v;
        
        for(int i=1;i<=M;i++) {
                if(L[i]>R[i]) continue;
                v.push_back({L[i],0,i});
                v.push_back({min(L[i]+K-1,R[i]-1),1,i});
                v.push_back({R[i],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) {

                } else {
                        int nxt=st.query(1,1,N,L[id],R[id]).second;
                        if(nxt!=0 && nxt!=id) {
                                root[id]=0;
                                adj[nxt].push_back(id);
                        }
                }
        }

        for(int i=1;i<=M;i++) {
                if(root[i] && L[i]<R[i]) dfs(i);
        }

        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.set(1,1,N,p,*pends[p].rbegin());
                } else if(t==1) { // query
                        nxt[p]=st.query(1,1,N,1,p).second;
                } else {
                        pends[L[id]].erase(make_pair(R[id],id));
                        st.set(1,1,N,L[id],*pends[L[id]].rbegin());
                }
        }

        for(int i=1;i<=Q;i++) {
                if(S[i]>T[i]) continue;

                int s=S[i], t=T[i];

                if(nxt[s]==0) {
                        ans[i]=-1;
                        continue;
                }

                if(R[nxt[s]]>=t) {
                        ans[i]=1;
                        continue;
                }

                int T=find(nxt[s],t);
                if(T==0) {
                        ans[i]=-1;
                        continue;
                }

                ans[i]=dep[nxt[s]]-dep[T]+1;
        }      
}

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

        cin>>N>>K>>M;
        for(int i=1;i<=M;i++) {
                cin>>L[i]>>R[i];
        }
        cin>>Q;
        for(int i=1;i<=Q;i++) {
                cin>>S[i]>>T[i];
        }

        work();

        for(int i=1;i<=M;i++) {
                L[i]=N-L[i]+1;
                R[i]=N-R[i]+1;
        }

        for(int i=1;i<=Q;i++) {
                S[i]=N-S[i]+1;
                T[i]=N-T[i]+1;
        }

        work();

        for(int i=1;i<=Q;i++) {
                cout<<ans[i]<<'\n';
        }
}

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