oj.uz

Submission #959458

# Submission time Handle Problem Language Result Execution time Memory
959458 2024-04-08T08:50:33 Z happy_node Railway Trip 2 (JOI22_ho_t4) C++17
35 / 100
 442 ms 62668 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 30452 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 30452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 25.0

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

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 60324 KB Output is correct
2 Correct 232 ms 53940 KB Output is correct
3 Correct 130 ms 43196 KB Output is correct
4 Correct 85 ms 37240 KB Output is correct
5 Correct 65 ms 33704 KB Output is correct
6 Correct 54 ms 33012 KB Output is correct
7 Correct 221 ms 49332 KB Output is correct
8 Correct 20 ms 30296 KB Output is correct
9 Correct 26 ms 30812 KB Output is correct
10 Correct 416 ms 60776 KB Output is correct
11 Correct 442 ms 62668 KB Output is correct
12 Correct 395 ms 60904 KB Output is correct
13 Correct 440 ms 62628 KB Output is correct
14 Correct 19 ms 30296 KB Output is correct
15 Correct 22 ms 30724 KB Output is correct
16 Correct 347 ms 59012 KB Output is correct
17 Correct 389 ms 59700 KB Output is correct
18 Correct 384 ms 59296 KB Output is correct
19 Correct 372 ms 59224 KB Output is correct

Subtask #6
0 / 13.0

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