oj.uz

Submission #959663

# Submission time Handle Problem Language Result Execution time Memory
959663 2024-04-08T16:35:00 Z happy_node Railway Trip 2 (JOI22_ho_t4) C++17
62 / 100
 1140 ms 80756 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;

                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;
                        }
                }

                auto [nxtL,nxtR]=ST[0].query(1,1,N,curL,curR);

                if(nxtL<=t&&t<=nxtR) {
                        cout<<ans+1<<'\n';
                } else {
                        cout<<-1<<'\n';
                }
        }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47704 KB Output is correct
2 Correct 8 ms 47704 KB Output is correct
3 Correct 7 ms 47708 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 9 ms 47704 KB Output is correct
6 Correct 7 ms 47792 KB Output is correct
7 Correct 8 ms 47800 KB Output is correct
8 Correct 7 ms 47708 KB Output is correct
9 Correct 9 ms 47708 KB Output is correct
10 Correct 6 ms 47708 KB Output is correct
11 Correct 9 ms 47792 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 8 ms 47704 KB Output is correct
2 Correct 8 ms 47704 KB Output is correct
3 Correct 7 ms 47708 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 9 ms 47704 KB Output is correct
6 Correct 7 ms 47792 KB Output is correct
7 Correct 8 ms 47800 KB Output is correct
8 Correct 7 ms 47708 KB Output is correct
9 Correct 9 ms 47708 KB Output is correct
10 Correct 6 ms 47708 KB Output is correct
11 Correct 9 ms 47792 KB Output is correct
12 Correct 8 ms 47708 KB Output is correct
13 Correct 22 ms 50000 KB Output is correct
14 Correct 21 ms 49756 KB Output is correct
15 Correct 15 ms 49756 KB Output is correct
16 Correct 16 ms 49756 KB Output is correct
17 Correct 23 ms 50208 KB Output is correct
18 Correct 16 ms 50012 KB Output is correct
19 Correct 18 ms 49820 KB Output is correct
20 Correct 16 ms 50000 KB Output is correct
21 Correct 12 ms 49752 KB Output is correct
22 Correct 18 ms 49756 KB Output is correct
23 Correct 21 ms 49756 KB Output is correct
24 Correct 21 ms 49972 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 74352 KB Output is correct
2 Correct 665 ms 74224 KB Output is correct
3 Correct 681 ms 75236 KB Output is correct
4 Correct 631 ms 73824 KB Output is correct
5 Correct 485 ms 77264 KB Output is correct
6 Correct 637 ms 75568 KB Output is correct
7 Correct 468 ms 77508 KB Output is correct
8 Correct 428 ms 74324 KB Output is correct
9 Correct 428 ms 74832 KB Output is correct
10 Correct 640 ms 74792 KB Output is correct
11 Correct 563 ms 76956 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 827 ms 75736 KB Output is correct
2 Incorrect 821 ms 78288 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 800 ms 78252 KB Output is correct
2 Correct 1140 ms 75764 KB Output is correct
3 Correct 1068 ms 72604 KB Output is correct
4 Correct 1049 ms 70612 KB Output is correct
5 Correct 902 ms 69564 KB Output is correct
6 Correct 908 ms 69116 KB Output is correct
7 Correct 742 ms 77620 KB Output is correct
8 Correct 7 ms 47704 KB Output is correct
9 Correct 19 ms 50012 KB Output is correct
10 Correct 668 ms 80520 KB Output is correct
11 Correct 911 ms 80656 KB Output is correct
12 Correct 841 ms 80756 KB Output is correct
13 Correct 894 ms 80416 KB Output is correct
14 Correct 7 ms 47704 KB Output is correct
15 Correct 22 ms 49756 KB Output is correct
16 Correct 703 ms 75412 KB Output is correct
17 Correct 1072 ms 77844 KB Output is correct
18 Correct 988 ms 75856 KB Output is correct
19 Correct 961 ms 76232 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47704 KB Output is correct
2 Correct 8 ms 47704 KB Output is correct
3 Correct 7 ms 47708 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 9 ms 47704 KB Output is correct
6 Correct 7 ms 47792 KB Output is correct
7 Correct 8 ms 47800 KB Output is correct
8 Correct 7 ms 47708 KB Output is correct
9 Correct 9 ms 47708 KB Output is correct
10 Correct 6 ms 47708 KB Output is correct
11 Correct 9 ms 47792 KB Output is correct
12 Correct 8 ms 47708 KB Output is correct
13 Correct 22 ms 50000 KB Output is correct
14 Correct 21 ms 49756 KB Output is correct
15 Correct 15 ms 49756 KB Output is correct
16 Correct 16 ms 49756 KB Output is correct
17 Correct 23 ms 50208 KB Output is correct
18 Correct 16 ms 50012 KB Output is correct
19 Correct 18 ms 49820 KB Output is correct
20 Correct 16 ms 50000 KB Output is correct
21 Correct 12 ms 49752 KB Output is correct
22 Correct 18 ms 49756 KB Output is correct
23 Correct 21 ms 49756 KB Output is correct
24 Correct 21 ms 49972 KB Output is correct
25 Correct 680 ms 74352 KB Output is correct
26 Correct 665 ms 74224 KB Output is correct
27 Correct 681 ms 75236 KB Output is correct
28 Correct 631 ms 73824 KB Output is correct
29 Correct 485 ms 77264 KB Output is correct
30 Correct 637 ms 75568 KB Output is correct
31 Correct 468 ms 77508 KB Output is correct
32 Correct 428 ms 74324 KB Output is correct
33 Correct 428 ms 74832 KB Output is correct
34 Correct 640 ms 74792 KB Output is correct
35 Correct 563 ms 76956 KB Output is correct
36 Correct 827 ms 75736 KB Output is correct
37 Incorrect 821 ms 78288 KB Output isn't correct
38 Halted 0 ms 0 KB -