oj.uz

Submission #959425

# Submission time Handle Problem Language Result Execution time Memory
959425 2024-04-08T07:39:51 Z happy_node Railway Trip 2 (JOI22_ho_t4) C++17
0 / 100
 457 ms 61612 KB 
#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];
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 main() {
        cin.tie(0); ios_base::sync_with_stdio(0);

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

        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) {
                                root[id]=0;
                                adj[nxt].push_back(id);
                        }
                }
        }

        for(int i=1;i<=M;i++) {
                if(root[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.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==0) {
                        cout<<-1<<'\n';
                        continue;
                }

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 35932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 35932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 167 ms 49080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 172 ms 49568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 59404 KB Output is correct
2 Correct 215 ms 58292 KB Output is correct
3 Correct 137 ms 48204 KB Output is correct
4 Correct 84 ms 44204 KB Output is correct
5 Correct 54 ms 38352 KB Output is correct
6 Correct 50 ms 37620 KB Output is correct
7 Correct 233 ms 51652 KB Output is correct
8 Correct 17 ms 35928 KB Output is correct
9 Correct 18 ms 36088 KB Output is correct
10 Correct 404 ms 59820 KB Output is correct
11 Incorrect 457 ms 61612 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 35932 KB Output isn't correct
2 Halted 0 ms 0 KB -