oj.uz

Submission #959449

# Submission time Handle Problem Language Result Execution time Memory
959449 2024-04-08T08:33:30 Z happy_node Railway Trip 2 (JOI22_ho_t4) C++17
0 / 100
 496 ms 62620 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 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];
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.set(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.set(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 19 ms 31320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 60404 KB Output is correct
2 Correct 249 ms 53804 KB Output is correct
3 Correct 150 ms 43204 KB Output is correct
4 Correct 89 ms 37316 KB Output is correct
5 Correct 61 ms 33728 KB Output is correct
6 Correct 55 ms 33000 KB Output is correct
7 Correct 251 ms 49312 KB Output is correct
8 Correct 19 ms 30296 KB Output is correct
9 Correct 21 ms 30808 KB Output is correct
10 Correct 453 ms 60652 KB Output is correct
11 Correct 496 ms 62620 KB Output is correct
12 Correct 455 ms 60836 KB Output is correct
13 Correct 461 ms 62572 KB Output is correct
14 Correct 19 ms 30296 KB Output is correct
15 Incorrect 22 ms 30708 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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