oj.uz

Submission #959667

# Submission time Handle Problem Language Result Execution time Memory
959667 2024-04-08T16:48:14 Z happy_node Railway Trip 2 (JOI22_ho_t4) C++17
62 / 100
 1084 ms 81052 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=1e5+5, MK=20;

int N,K,M,Q;

int L[MX],R[MX], A[MX], B[MX];

struct segtree {
        pair<int,int> t[4 * MX];
        // I define t[v] to be the range within reach from v by using 2^k steps

        pair<int,int> merge(pair<int,int> a, pair<int, int> b) {
                int l=min(a.first,b.first);
                int r=max(a.second,b.second);
                return make_pair(l,r);
        }
 
        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] = merge(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(1e9,0);
                if(ql <= l && qr >= r) return t[v];
                int mid = (l + r) >> 1;
                return merge(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(1e9,0);
        }
} ST[MK];

vector<int> opens[MX], closes[MX];

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

        cin>>N>>K>>M;
        for(int i=1;i<=M;i++) {
                cin>>A[i]>>B[i];
                if(A[i]<B[i]) {
                        opens[A[i]].push_back(B[i]);
                        closes[min(A[i]+K-1,B[i]-1)].push_back(B[i]);
                } 
        }

        multiset<int> st;
        for(int i=1;i<=N;i++) {
                for(auto j:opens[i]) {
                        st.insert(j);
                }
                if(st.size())
                        R[i]=*st.rbegin();
                else
                        R[i]=i;
                for(auto j:closes[i]) {
                        st.erase(st.find(j));
                }
        }

        for(int i=1;i<=N;i++) {
                opens[i].clear();
                closes[i].clear();
        }

        for(int i=1;i<=M;i++) {
                if(A[i]>B[i]) {
                        opens[A[i]].push_back(B[i]);
                        closes[max(A[i]-K+1,B[i]+1)].push_back(B[i]);
                }
        }

        st.clear();
        for(int i=N;i>=1;i--) {
                for(auto j:opens[i]) {
                        st.insert(j);
                }       
                if(st.size())
                        L[i]=*st.begin();
                else
                        L[i]=i;
                for(auto j:closes[i]) {
                        st.erase(st.find(j));
                }
        }

        for(int i=1;i<=N;i++) {
                ST[0].update(1,1,N,i,make_pair(L[i],R[i]));
        }

        for(int k=1;k<MK;k++) {
                for(int i=1;i<=N;i++) {
                        auto [l,r]=ST[k-1].query(1,1,N,i,i);
                        auto [nxtL,nxtR]=ST[k-1].query(1,1,N,l,r);
                        ST[k].update(1,1,N,i,make_pair(nxtL,nxtR));
                }
        }

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

                auto [l,r]=ST[MK-1].query(1,1,N,s,s);

                if(t<l||t>r) {
                        cout<<-1<<'\n';
                        continue;
                }

                int curL=s,curR=s,ans=0;
                for(int k=MK-1;k>=0;k--) {
                        int nxtL=ST[k].query(1,1,N,curL,curR).first;
                        int nxtR=ST[k].query(1,1,N,curL,curR).second;

                        if(!(nxtL<=t&&t<=nxtR)) {
                                ans+=1<<k;
                                curL=nxtL;
                                curR=nxtR;
                        }
                }

                cout<<ans+1<<'\n';
        }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47696 KB Output is correct
2 Correct 12 ms 47836 KB Output is correct
3 Correct 8 ms 47784 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 8 ms 47812 KB Output is correct
6 Correct 7 ms 47708 KB Output is correct
7 Correct 7 ms 47708 KB Output is correct
8 Correct 11 ms 47708 KB Output is correct
9 Correct 9 ms 47704 KB Output is correct
10 Correct 7 ms 47708 KB Output is correct
11 Correct 7 ms 47708 KB Output is correct
12 Correct 8 ms 47708 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47696 KB Output is correct
2 Correct 12 ms 47836 KB Output is correct
3 Correct 8 ms 47784 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 8 ms 47812 KB Output is correct
6 Correct 7 ms 47708 KB Output is correct
7 Correct 7 ms 47708 KB Output is correct
8 Correct 11 ms 47708 KB Output is correct
9 Correct 9 ms 47704 KB Output is correct
10 Correct 7 ms 47708 KB Output is correct
11 Correct 7 ms 47708 KB Output is correct
12 Correct 8 ms 47708 KB Output is correct
13 Correct 21 ms 49756 KB Output is correct
14 Correct 19 ms 49920 KB Output is correct
15 Correct 16 ms 49756 KB Output is correct
16 Correct 14 ms 49756 KB Output is correct
17 Correct 22 ms 49756 KB Output is correct
18 Correct 16 ms 50008 KB Output is correct
19 Correct 18 ms 49756 KB Output is correct
20 Correct 20 ms 49756 KB Output is correct
21 Correct 13 ms 49756 KB Output is correct
22 Correct 22 ms 49960 KB Output is correct
23 Correct 19 ms 49972 KB Output is correct
24 Correct 19 ms 49756 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 74300 KB Output is correct
2 Correct 659 ms 74220 KB Output is correct
3 Correct 677 ms 75332 KB Output is correct
4 Correct 631 ms 73912 KB Output is correct
5 Correct 522 ms 77560 KB Output is correct
6 Correct 629 ms 75584 KB Output is correct
7 Correct 451 ms 77556 KB Output is correct
8 Correct 422 ms 74548 KB Output is correct
9 Correct 424 ms 74436 KB Output is correct
10 Correct 620 ms 74780 KB Output is correct
11 Correct 544 ms 77404 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 75884 KB Output is correct
2 Incorrect 635 ms 78416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 78348 KB Output is correct
2 Correct 1084 ms 75976 KB Output is correct
3 Correct 1045 ms 72576 KB Output is correct
4 Correct 1004 ms 70580 KB Output is correct
5 Correct 875 ms 69648 KB Output is correct
6 Correct 887 ms 69360 KB Output is correct
7 Correct 769 ms 77656 KB Output is correct
8 Correct 8 ms 47708 KB Output is correct
9 Correct 18 ms 50012 KB Output is correct
10 Correct 670 ms 80584 KB Output is correct
11 Correct 808 ms 80748 KB Output is correct
12 Correct 819 ms 80768 KB Output is correct
13 Correct 843 ms 81052 KB Output is correct
14 Correct 7 ms 47768 KB Output is correct
15 Correct 21 ms 49956 KB Output is correct
16 Correct 706 ms 75648 KB Output is correct
17 Correct 1027 ms 77920 KB Output is correct
18 Correct 975 ms 75860 KB Output is correct
19 Correct 947 ms 75956 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47696 KB Output is correct
2 Correct 12 ms 47836 KB Output is correct
3 Correct 8 ms 47784 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 8 ms 47812 KB Output is correct
6 Correct 7 ms 47708 KB Output is correct
7 Correct 7 ms 47708 KB Output is correct
8 Correct 11 ms 47708 KB Output is correct
9 Correct 9 ms 47704 KB Output is correct
10 Correct 7 ms 47708 KB Output is correct
11 Correct 7 ms 47708 KB Output is correct
12 Correct 8 ms 47708 KB Output is correct
13 Correct 21 ms 49756 KB Output is correct
14 Correct 19 ms 49920 KB Output is correct
15 Correct 16 ms 49756 KB Output is correct
16 Correct 14 ms 49756 KB Output is correct
17 Correct 22 ms 49756 KB Output is correct
18 Correct 16 ms 50008 KB Output is correct
19 Correct 18 ms 49756 KB Output is correct
20 Correct 20 ms 49756 KB Output is correct
21 Correct 13 ms 49756 KB Output is correct
22 Correct 22 ms 49960 KB Output is correct
23 Correct 19 ms 49972 KB Output is correct
24 Correct 19 ms 49756 KB Output is correct
25 Correct 675 ms 74300 KB Output is correct
26 Correct 659 ms 74220 KB Output is correct
27 Correct 677 ms 75332 KB Output is correct
28 Correct 631 ms 73912 KB Output is correct
29 Correct 522 ms 77560 KB Output is correct
30 Correct 629 ms 75584 KB Output is correct
31 Correct 451 ms 77556 KB Output is correct
32 Correct 422 ms 74548 KB Output is correct
33 Correct 424 ms 74436 KB Output is correct
34 Correct 620 ms 74780 KB Output is correct
35 Correct 544 ms 77404 KB Output is correct
36 Correct 804 ms 75884 KB Output is correct
37 Incorrect 635 ms 78416 KB Output isn't correct
38 Halted 0 ms 0 KB -