oj.uz

Submission #125497

# Submission time Handle Problem Language Result Execution time Memory
125497 2019-07-05T13:41:10 Z choikiwon Railway Trip (JOI17_railway_trip) C++17
100 / 100
 287 ms 19284 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MN = 100010;

int N, K, Q;
int L[MN];
int le[20][MN], ri[20][MN];

int main() {
    scanf("%d %d %d", &N, &K, &Q);

    for(int i = 0; i < N; i++) {
        scanf("%d", &L[i]);
        L[i]--;
    }

    stack<pii> stk;
    for(int i = 0; i < N; i++) {
        while(!stk.empty() && stk.top().first < L[i]) stk.pop();
        if(!stk.empty()) le[0][i] = stk.top().second;
        stk.push(pii(L[i], i));
    }
    while(!stk.empty()) stk.pop();

    for(int i = N - 1; i >= 0; i--) {
        while(!stk.empty() && stk.top().first < L[i]) stk.pop();
        if(!stk.empty()) ri[0][i] = stk.top().second;
        stk.push(pii(L[i], i));
    }

    le[0][0] = 0;
    ri[0][N - 1] = N - 1;

    for(int i = 1; i < 20; i++) {
        for(int j = 0; j < N; j++) {
            int t = le[i - 1][j];
            int d = ri[i - 1][j];
            le[i][j] = min(le[i - 1][t], le[i - 1][d]);
            ri[i][j] = max(ri[i - 1][t], ri[i - 1][d]);
        }
    }

    for(int i = 0; i < Q; i++) {
        int a, b; scanf("%d %d", &a, &b);
        a--; b--;
        if(a > b) swap(a, b);

        int ans = 0;
        int l = a;
        int r = a;
        for(int j = 20; j--;) {
            if(max(ri[j][l], ri[j][r]) < b) {
                ans += (1 << j);
                int nl = min(le[j][l], le[j][r]);
                int nr = max(ri[j][l], ri[j][r]);
                l = nl;
                r = nr;
            }
        }

        a = r;
        l = b;
        r = b;
        for(int j = 20; j--;) {
            if(min(le[j][l], le[j][r]) > a) {
                ans += (1 << j);
                int nl = min(le[j][l], le[j][r]);
                int nr = max(ri[j][l], ri[j][r]);
                l = nl;
                r = nr;
            }
        }
        printf("%d\n", ans);
    }
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &K, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &L[i]);
         ~~~~~^~~~~~~~~~~~~
railway_trip.cpp:47:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d %d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 33 ms 16632 KB Output is correct
3 Correct 33 ms 16632 KB Output is correct
4 Correct 33 ms 16632 KB Output is correct
5 Correct 33 ms 16760 KB Output is correct
6 Correct 34 ms 16824 KB Output is correct
7 Correct 36 ms 16888 KB Output is correct
8 Correct 35 ms 17236 KB Output is correct
9 Correct 45 ms 17300 KB Output is correct
10 Correct 32 ms 17272 KB Output is correct
11 Correct 35 ms 17272 KB Output is correct
12 Correct 35 ms 17272 KB Output is correct
13 Correct 35 ms 17200 KB Output is correct
14 Correct 35 ms 17272 KB Output is correct
15 Correct 35 ms 17400 KB Output is correct
16 Correct 35 ms 17184 KB Output is correct
17 Correct 34 ms 16888 KB Output is correct
18 Correct 34 ms 17016 KB Output is correct
19 Correct 33 ms 17016 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 17076 KB Output is correct
2 Correct 228 ms 18280 KB Output is correct
3 Correct 171 ms 18296 KB Output is correct
4 Correct 159 ms 18296 KB Output is correct
5 Correct 175 ms 18248 KB Output is correct
6 Correct 176 ms 18428 KB Output is correct
7 Correct 166 ms 18296 KB Output is correct
8 Correct 196 ms 18656 KB Output is correct
9 Correct 272 ms 18840 KB Output is correct
10 Correct 237 ms 18900 KB Output is correct
11 Correct 230 ms 18900 KB Output is correct
12 Correct 287 ms 18872 KB Output is correct
13 Correct 246 ms 18868 KB Output is correct
14 Correct 186 ms 18424 KB Output is correct
15 Correct 166 ms 18244 KB Output is correct
16 Correct 163 ms 18292 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 16636 KB Output is correct
2 Correct 145 ms 18356 KB Output is correct
3 Correct 144 ms 18388 KB Output is correct
4 Correct 135 ms 18424 KB Output is correct
5 Correct 241 ms 18964 KB Output is correct
6 Correct 185 ms 19076 KB Output is correct
7 Correct 182 ms 19284 KB Output is correct
8 Correct 201 ms 19064 KB Output is correct
9 Correct 187 ms 19036 KB Output is correct
10 Correct 185 ms 18936 KB Output is correct
11 Correct 180 ms 19064 KB Output is correct
12 Correct 184 ms 19068 KB Output is correct
13 Correct 192 ms 18936 KB Output is correct
14 Correct 240 ms 19064 KB Output is correct
15 Correct 195 ms 18936 KB Output is correct
16 Correct 185 ms 18936 KB Output is correct
17 Correct 178 ms 18920 KB Output is correct
18 Correct 169 ms 18940 KB Output is correct
19 Correct 170 ms 18908 KB Output is correct
20 Correct 164 ms 18508 KB Output is correct
21 Correct 131 ms 18396 KB Output is correct
22 Correct 129 ms 18412 KB Output is correct
23 Correct 125 ms 18424 KB Output is correct