oj.uz

Submission #1085299

# Submission time Handle Problem Language Result Execution time Memory
1085299 2024-09-07T22:04:02 Z veehj Railway Trip (JOI17_railway_trip) C++17
100 / 100
 419 ms 55896 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define sz(a) (ll)a.size()
#define all(x) (x).begin(), (x).end()

int main() {
    ll n, k, q; cin >> n >> k >> q;
    vector<ll> lvl(n); for(auto& u : lvl) cin >> u;
    vector<vector<vector<ll>>> stp(2, vector<vector<ll>>(n, vector<ll>(18, 0LL))); //v[left/right][place][2^?]=first point place will reach
    stack<ll> st;
    for(ll i=0; i<n; i++){
        while(!st.empty() && lvl[st.top()]<lvl[i]) st.pop();
        if(st.empty()) stp[0][i][0]=i;
        else stp[0][i][0]=st.top();
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for(ll i=n-1; i>=0; i--){
        while(!st.empty() && lvl[st.top()]<lvl[i]) st.pop();
        if(st.empty()) stp[1][i][0]=i;
        else stp[1][i][0]=st.top();
        st.push(i);
    }
    for(int i=1; i<=17; i++){
        for(ll j=0; j<n; j++){
            stp[0][j][i]=min(stp[0][stp[0][j][i-1]][i-1], stp[0][stp[1][j][i-1]][i-1]);
            stp[1][j][i]=max(stp[1][stp[0][j][i-1]][i-1], stp[1][stp[1][j][i-1]][i-1]);
        }
    }
    while(q--){
        ll ans=0;
        //find the 2 sticked range
        ll a, b, l, r; cin >> a >> b;
        a--; b--;
        if(a>b) swap(a, b);
        l=r=a;
        for(int i=17; i>=0; i--){
            ll u=min(stp[0][l][i], stp[0][r][i]), v=max(stp[1][l][i], stp[1][r][i]);
            if(v<b){
                l=u, r=v;
                ans+=pow(2, i);
            }
        }
        a=r;
        l=r=b;
        for(int i=17; i>=0; i--){
            ll u=min(stp[0][l][i], stp[0][r][i]), v=max(stp[1][l][i], stp[1][r][i]);
            if(a<u){
                l=u, r=v;
                ans+=pow(2, i);
            }
        }
        //no need +1
        cout << ans << endl;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 66 ms 55192 KB Output is correct
3 Correct 63 ms 55380 KB Output is correct
4 Correct 63 ms 55376 KB Output is correct
5 Correct 61 ms 55384 KB Output is correct
6 Correct 63 ms 55448 KB Output is correct
7 Correct 64 ms 55632 KB Output is correct
8 Correct 64 ms 55376 KB Output is correct
9 Correct 74 ms 55572 KB Output is correct
10 Correct 71 ms 55408 KB Output is correct
11 Correct 68 ms 55632 KB Output is correct
12 Correct 76 ms 55632 KB Output is correct
13 Correct 68 ms 55648 KB Output is correct
14 Correct 75 ms 55632 KB Output is correct
15 Correct 70 ms 55732 KB Output is correct
16 Correct 68 ms 55608 KB Output is correct
17 Correct 69 ms 55632 KB Output is correct
18 Correct 71 ms 55632 KB Output is correct
19 Correct 68 ms 55636 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 55376 KB Output is correct
2 Correct 299 ms 55376 KB Output is correct
3 Correct 311 ms 55376 KB Output is correct
4 Correct 308 ms 55380 KB Output is correct
5 Correct 300 ms 55572 KB Output is correct
6 Correct 289 ms 55636 KB Output is correct
7 Correct 295 ms 55632 KB Output is correct
8 Correct 353 ms 55376 KB Output is correct
9 Correct 382 ms 55380 KB Output is correct
10 Correct 374 ms 55380 KB Output is correct
11 Correct 399 ms 55356 KB Output is correct
12 Correct 385 ms 55380 KB Output is correct
13 Correct 419 ms 55480 KB Output is correct
14 Correct 365 ms 55376 KB Output is correct
15 Correct 332 ms 55460 KB Output is correct
16 Correct 292 ms 55472 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 55812 KB Output is correct
2 Correct 268 ms 55892 KB Output is correct
3 Correct 283 ms 55604 KB Output is correct
4 Correct 277 ms 55892 KB Output is correct
5 Correct 406 ms 55356 KB Output is correct
6 Correct 339 ms 55892 KB Output is correct
7 Correct 346 ms 55872 KB Output is correct
8 Correct 340 ms 55636 KB Output is correct
9 Correct 323 ms 55896 KB Output is correct
10 Correct 325 ms 55892 KB Output is correct
11 Correct 320 ms 55892 KB Output is correct
12 Correct 310 ms 55892 KB Output is correct
13 Correct 302 ms 55892 KB Output is correct
14 Correct 336 ms 55892 KB Output is correct
15 Correct 326 ms 55892 KB Output is correct
16 Correct 327 ms 55892 KB Output is correct
17 Correct 327 ms 55892 KB Output is correct
18 Correct 337 ms 55892 KB Output is correct
19 Correct 330 ms 55892 KB Output is correct
20 Correct 308 ms 55892 KB Output is correct
21 Correct 290 ms 55896 KB Output is correct
22 Correct 271 ms 55892 KB Output is correct
23 Correct 288 ms 55892 KB Output is correct