oj.uz

Submission #534811

# Submission time Handle Problem Language Result Execution time Memory
534811 2022-03-09T02:50:05 Z i_am_noob Railway Trip 2 (JOI22_ho_t4) C++17
100 / 100
 323 ms 260848 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")

#define ll long long
//#define int ll
#define ull unsigned ll
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define chkmin(a,b) (a=min(a,b))
#define chkmax(a,b) (a=max(a,b))
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
//#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif

const int mod=1000000007;
const int maxn=100005,maxm=18,maxk=7777714;

//i_am_noob
int n,k,m,l[maxm][maxn],r[maxm][maxn],spl[maxm][maxm][maxn],spr[maxm][maxm][maxn];

int queryl(int p, int l, int r){int k=__lg(r-l+1); return min(spl[p][k][l],spl[p][k][r-pow2(k)+1]);}
int queryr(int p, int l, int r){int k=__lg(r-l+1); return max(spr[p][k][l],spr[p][k][r-pow2(k)+1]);}

void orzck(){
    cin >> n >> k >> m;
    vector<vector<int>> addr(n+1),subr(n+1),addl(n+1),subl(n+1);
    rep(m){
        int u,v;
        cin >> u >> v;
        u--,v--;
        if(u<v) addr[u].pb(v),subr[min(u+k,v)].pb(v);
        else addl[u].pb(v),subl[max(u-k,v)].pb(v);
    }
    multiset<int> st;
    rep(n){
        for(auto j: addr[i]) st.insert(j);
        for(auto j: subr[i]) st.erase(st.find(j));
        if(st.empty()) r[0][i]=i;
        else r[0][i]=*st.rbegin();
    }
    st.clear();
    rep3(i,n-1,0){
        for(auto j: addl[i]) st.insert(j);
        for(auto j: subl[i]) st.erase(st.find(j));
        if(st.empty()) l[0][i]=i;
        else l[0][i]=*st.begin();
    }
    
    rep2(j,1,maxm+1){
        rep(n) spl[j-1][0][i]=l[j-1][i],spr[j-1][0][i]=r[j-1][i];
        rep2(jj,1,maxm) rep(n-pow2(jj)+1) spl[j-1][jj][i]=min(spl[j-1][jj-1][i],spl[j-1][jj-1][i+pow2(jj-1)]);
        rep2(jj,1,maxm) rep(n-pow2(jj)+1) spr[j-1][jj][i]=max(spr[j-1][jj-1][i],spr[j-1][jj-1][i+pow2(jj-1)]);
        if(j==maxm) break;
        rep(n) l[j][i]=queryl(j-1,l[j-1][i],r[j-1][i]),r[j][i]=queryr(j-1,l[j-1][i],r[j-1][i]);
    }
    int q;
    cin >> q;
    while(q--){
        int s,t;
        cin >> s >> t;
        s--,t--;
        int res=0,curl=s,curr=s;
        if(s<t){
            rep3(i,maxm-1,0){
                int nl=queryl(i,curl,curr),nr=queryr(i,curl,curr);
                if(nr<t){
                    curl=nl,curr=nr;
                    res+=pow2(i);
                }
            }
            res++;
        }
        else{
            rep3(i,maxm-1,0){
                int nl=queryl(i,curl,curr),nr=queryr(i,curl,curr);
                if(nl>t){
                    curl=nl,curr=nr;
                    res+=pow2(i);
                }
            }
            res++;
        }
        if(res>n) cout << "-1\n";
        else cout << res << "\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    orzck();
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2508 KB Output is correct
2 Correct 2 ms 2508 KB Output is correct
3 Correct 1 ms 2496 KB Output is correct
4 Correct 2 ms 2496 KB Output is correct
5 Correct 2 ms 2508 KB Output is correct
6 Correct 1 ms 2508 KB Output is correct
7 Correct 2 ms 2500 KB Output is correct
8 Correct 2 ms 2496 KB Output is correct
9 Correct 2 ms 2508 KB Output is correct
10 Correct 1 ms 828 KB Output is correct
11 Correct 2 ms 2508 KB Output is correct
12 Correct 1 ms 2500 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2508 KB Output is correct
2 Correct 2 ms 2508 KB Output is correct
3 Correct 1 ms 2496 KB Output is correct
4 Correct 2 ms 2496 KB Output is correct
5 Correct 2 ms 2508 KB Output is correct
6 Correct 1 ms 2508 KB Output is correct
7 Correct 2 ms 2500 KB Output is correct
8 Correct 2 ms 2496 KB Output is correct
9 Correct 2 ms 2508 KB Output is correct
10 Correct 1 ms 828 KB Output is correct
11 Correct 2 ms 2508 KB Output is correct
12 Correct 1 ms 2500 KB Output is correct
13 Correct 5 ms 5836 KB Output is correct
14 Correct 4 ms 5832 KB Output is correct
15 Correct 3 ms 5832 KB Output is correct
16 Correct 4 ms 5768 KB Output is correct
17 Correct 4 ms 5836 KB Output is correct
18 Correct 4 ms 5836 KB Output is correct
19 Correct 5 ms 5708 KB Output is correct
20 Correct 4 ms 5836 KB Output is correct
21 Correct 4 ms 5836 KB Output is correct
22 Correct 5 ms 5844 KB Output is correct
23 Correct 4 ms 5836 KB Output is correct
24 Correct 6 ms 5820 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 252100 KB Output is correct
2 Correct 137 ms 251824 KB Output is correct
3 Correct 170 ms 253104 KB Output is correct
4 Correct 145 ms 251520 KB Output is correct
5 Correct 261 ms 256596 KB Output is correct
6 Correct 261 ms 260848 KB Output is correct
7 Correct 200 ms 259820 KB Output is correct
8 Correct 191 ms 251716 KB Output is correct
9 Correct 185 ms 252948 KB Output is correct
10 Correct 243 ms 256228 KB Output is correct
11 Correct 236 ms 256324 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 253972 KB Output is correct
2 Correct 292 ms 257312 KB Output is correct
3 Correct 198 ms 254144 KB Output is correct
4 Correct 223 ms 260276 KB Output is correct
5 Correct 310 ms 257144 KB Output is correct
6 Correct 295 ms 258396 KB Output is correct
7 Correct 260 ms 256956 KB Output is correct
8 Correct 287 ms 257092 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 256580 KB Output is correct
2 Correct 234 ms 254184 KB Output is correct
3 Correct 196 ms 250480 KB Output is correct
4 Correct 204 ms 248364 KB Output is correct
5 Correct 155 ms 247128 KB Output is correct
6 Correct 139 ms 246788 KB Output is correct
7 Correct 173 ms 256032 KB Output is correct
8 Correct 1 ms 2472 KB Output is correct
9 Correct 4 ms 5836 KB Output is correct
10 Correct 294 ms 256564 KB Output is correct
11 Correct 296 ms 258632 KB Output is correct
12 Correct 295 ms 253984 KB Output is correct
13 Correct 290 ms 256068 KB Output is correct
14 Correct 2 ms 2508 KB Output is correct
15 Correct 4 ms 5836 KB Output is correct
16 Correct 217 ms 251784 KB Output is correct
17 Correct 283 ms 251972 KB Output is correct
18 Correct 297 ms 252016 KB Output is correct
19 Correct 250 ms 252008 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2508 KB Output is correct
2 Correct 2 ms 2508 KB Output is correct
3 Correct 1 ms 2496 KB Output is correct
4 Correct 2 ms 2496 KB Output is correct
5 Correct 2 ms 2508 KB Output is correct
6 Correct 1 ms 2508 KB Output is correct
7 Correct 2 ms 2500 KB Output is correct
8 Correct 2 ms 2496 KB Output is correct
9 Correct 2 ms 2508 KB Output is correct
10 Correct 1 ms 828 KB Output is correct
11 Correct 2 ms 2508 KB Output is correct
12 Correct 1 ms 2500 KB Output is correct
13 Correct 5 ms 5836 KB Output is correct
14 Correct 4 ms 5832 KB Output is correct
15 Correct 3 ms 5832 KB Output is correct
16 Correct 4 ms 5768 KB Output is correct
17 Correct 4 ms 5836 KB Output is correct
18 Correct 4 ms 5836 KB Output is correct
19 Correct 5 ms 5708 KB Output is correct
20 Correct 4 ms 5836 KB Output is correct
21 Correct 4 ms 5836 KB Output is correct
22 Correct 5 ms 5844 KB Output is correct
23 Correct 4 ms 5836 KB Output is correct
24 Correct 6 ms 5820 KB Output is correct
25 Correct 138 ms 252100 KB Output is correct
26 Correct 137 ms 251824 KB Output is correct
27 Correct 170 ms 253104 KB Output is correct
28 Correct 145 ms 251520 KB Output is correct
29 Correct 261 ms 256596 KB Output is correct
30 Correct 261 ms 260848 KB Output is correct
31 Correct 200 ms 259820 KB Output is correct
32 Correct 191 ms 251716 KB Output is correct
33 Correct 185 ms 252948 KB Output is correct
34 Correct 243 ms 256228 KB Output is correct
35 Correct 236 ms 256324 KB Output is correct
36 Correct 197 ms 253972 KB Output is correct
37 Correct 292 ms 257312 KB Output is correct
38 Correct 198 ms 254144 KB Output is correct
39 Correct 223 ms 260276 KB Output is correct
40 Correct 310 ms 257144 KB Output is correct
41 Correct 295 ms 258396 KB Output is correct
42 Correct 260 ms 256956 KB Output is correct
43 Correct 287 ms 257092 KB Output is correct
44 Correct 313 ms 256580 KB Output is correct
45 Correct 234 ms 254184 KB Output is correct
46 Correct 196 ms 250480 KB Output is correct
47 Correct 204 ms 248364 KB Output is correct
48 Correct 155 ms 247128 KB Output is correct
49 Correct 139 ms 246788 KB Output is correct
50 Correct 173 ms 256032 KB Output is correct
51 Correct 1 ms 2472 KB Output is correct
52 Correct 4 ms 5836 KB Output is correct
53 Correct 294 ms 256564 KB Output is correct
54 Correct 296 ms 258632 KB Output is correct
55 Correct 295 ms 253984 KB Output is correct
56 Correct 290 ms 256068 KB Output is correct
57 Correct 2 ms 2508 KB Output is correct
58 Correct 4 ms 5836 KB Output is correct
59 Correct 217 ms 251784 KB Output is correct
60 Correct 283 ms 251972 KB Output is correct
61 Correct 297 ms 252016 KB Output is correct
62 Correct 250 ms 252008 KB Output is correct
63 Correct 203 ms 250840 KB Output is correct
64 Correct 206 ms 251912 KB Output is correct
65 Correct 214 ms 251120 KB Output is correct
66 Correct 316 ms 255080 KB Output is correct
67 Correct 283 ms 259036 KB Output is correct
68 Correct 281 ms 252732 KB Output is correct
69 Correct 299 ms 255696 KB Output is correct
70 Correct 254 ms 254288 KB Output is correct
71 Correct 323 ms 254296 KB Output is correct