oj.uz

Submission #125506

# Submission time Handle Problem Language Result Execution time Memory
125506 2019-07-05T13:56:45 Z choikiwon Railway Trip (JOI17_railway_trip) C++17
100 / 100
 273 ms 18608 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 508 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 4 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 32 ms 16632 KB Output is correct
3 Correct 33 ms 16632 KB Output is correct
4 Correct 34 ms 16632 KB Output is correct
5 Correct 34 ms 16708 KB Output is correct
6 Correct 35 ms 16896 KB Output is correct
7 Correct 36 ms 16888 KB Output is correct
8 Correct 31 ms 17072 KB Output is correct
9 Correct 34 ms 17428 KB Output is correct
10 Correct 32 ms 17528 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 17272 KB Output is correct
14 Correct 35 ms 17272 KB Output is correct
15 Correct 35 ms 17272 KB Output is correct
16 Correct 35 ms 17252 KB Output is correct
17 Correct 36 ms 17016 KB Output is correct
18 Correct 47 ms 16988 KB Output is correct
19 Correct 34 ms 16888 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 17012 KB Output is correct
2 Correct 186 ms 17912 KB Output is correct
3 Correct 263 ms 17784 KB Output is correct
4 Correct 173 ms 17912 KB Output is correct
5 Correct 166 ms 17784 KB Output is correct
6 Correct 167 ms 17872 KB Output is correct
7 Correct 174 ms 17784 KB Output is correct
8 Correct 197 ms 18320 KB Output is correct
9 Correct 210 ms 18392 KB Output is correct
10 Correct 245 ms 18352 KB Output is correct
11 Correct 228 ms 18608 KB Output is correct
12 Correct 237 ms 18516 KB Output is correct
13 Correct 238 ms 18484 KB Output is correct
14 Correct 211 ms 18040 KB Output is correct
15 Correct 163 ms 17784 KB Output is correct
16 Correct 166 ms 17656 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 16760 KB Output is correct
2 Correct 136 ms 17556 KB Output is correct
3 Correct 132 ms 17528 KB Output is correct
4 Correct 176 ms 17528 KB Output is correct
5 Correct 240 ms 18492 KB Output is correct
6 Correct 184 ms 18172 KB Output is correct
7 Correct 273 ms 18296 KB Output is correct
8 Correct 199 ms 18424 KB Output is correct
9 Correct 176 ms 18036 KB Output is correct
10 Correct 182 ms 18068 KB Output is correct
11 Correct 187 ms 18140 KB Output is correct
12 Correct 181 ms 18296 KB Output is correct
13 Correct 166 ms 18040 KB Output is correct
14 Correct 183 ms 18048 KB Output is correct
15 Correct 201 ms 18184 KB Output is correct
16 Correct 186 ms 18224 KB Output is correct
17 Correct 173 ms 18052 KB Output is correct
18 Correct 180 ms 17952 KB Output is correct
19 Correct 187 ms 17912 KB Output is correct
20 Correct 161 ms 17644 KB Output is correct
21 Correct 129 ms 17500 KB Output is correct
22 Correct 133 ms 17528 KB Output is correct
23 Correct 135 ms 17500 KB Output is correct