oj.uz

Submission #114147

# Submission time Handle Problem Language Result Execution time Memory
114147 2019-05-30T16:23:05 Z popovicirobert Railway Trip (JOI17_railway_trip) C++14
100 / 100
 451 ms 23804 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;


int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int n, k, q, i;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k >> q;

    vector <int> h(n + 1);
    for(i = 1; i <= n; i++) {
        cin >> h[i];
    }

    vector < vector <int> > l(n + 1, vector <int>(17)), r(n + 1, vector <int>(17));
    vector <int> stk;

    for(i = 1; i <= n; i++) {
        while(stk.size() && h[stk.back()] < h[i]) {
            stk.pop_back();
        }
        if(stk.size()) {
            l[i][0] = stk.back();
        }
        else {
            l[i][0] = 1;
        }
        stk.push_back(i);
    }

    stk.clear();

    for(i = n; i >= 1; i--) {
        while(stk.size() && h[stk.back()] < h[i]) {
            stk.pop_back();
        }
        if(stk.size()) {
            r[i][0] = stk.back();
        }
        else {
            r[i][0] = n;
        }
        stk.push_back(i);
    }

    for(int bit = 1; bit <= 16; bit++) {
        for(i = 1; i <= n; i++) {
            l[i][bit] = min(l[l[i][bit - 1]][bit - 1], l[r[i][bit - 1]][bit - 1]);
            r[i][bit] = max(r[r[i][bit - 1]][bit - 1], r[l[i][bit - 1]][bit - 1]);

            if(l[i][bit] == 0) {
                l[i][bit] = 1;
            }
            if(r[i][bit] == 0) {
                r[i][bit] = n;
            }
        }
    }

    while(q--) {
        int x, y;
        cin >> x >> y;

        if(x > y) swap(x, y);

        int left = x, right = x;
        int ans = 0;

        for(int bit = 16; bit >= 0; bit--) {
            int curl = min(l[left][bit], l[right][bit]);
            int curr = max(r[left][bit], r[right][bit]);

            if(curr < y) {
                ans += (1 << bit);
                left = curl;
                right = curr;
            }
        }

        int pos = right;
        left = right = y;

        for(int bit = 16; bit >= 0; bit--) {
            int curl = min(l[left][bit], l[right][bit]);
            int curr = max(r[left][bit], r[right][bit]);

            if(curl > pos) {
                ans += (1 << bit);
                left = curl;
                right = curr;
            }
        }

        cout << ans << "\n";
    }

    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 77 ms 21488 KB Output is correct
3 Correct 85 ms 21368 KB Output is correct
4 Correct 65 ms 21496 KB Output is correct
5 Correct 67 ms 21368 KB Output is correct
6 Correct 65 ms 21504 KB Output is correct
7 Correct 69 ms 21752 KB Output is correct
8 Correct 79 ms 21876 KB Output is correct
9 Correct 101 ms 22140 KB Output is correct
10 Correct 88 ms 22132 KB Output is correct
11 Correct 86 ms 22012 KB Output is correct
12 Correct 112 ms 22008 KB Output is correct
13 Correct 75 ms 22008 KB Output is correct
14 Correct 75 ms 22016 KB Output is correct
15 Correct 84 ms 22008 KB Output is correct
16 Correct 95 ms 22012 KB Output is correct
17 Correct 94 ms 21740 KB Output is correct
18 Correct 86 ms 21624 KB Output is correct
19 Correct 71 ms 21752 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 23032 KB Output is correct
2 Correct 239 ms 23032 KB Output is correct
3 Correct 232 ms 23156 KB Output is correct
4 Correct 221 ms 23032 KB Output is correct
5 Correct 220 ms 23032 KB Output is correct
6 Correct 222 ms 23160 KB Output is correct
7 Correct 228 ms 23004 KB Output is correct
8 Correct 357 ms 23368 KB Output is correct
9 Correct 451 ms 23536 KB Output is correct
10 Correct 391 ms 23792 KB Output is correct
11 Correct 348 ms 23568 KB Output is correct
12 Correct 409 ms 23536 KB Output is correct
13 Correct 406 ms 23664 KB Output is correct
14 Correct 344 ms 23320 KB Output is correct
15 Correct 260 ms 23024 KB Output is correct
16 Correct 284 ms 22904 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 23236 KB Output is correct
2 Correct 177 ms 23148 KB Output is correct
3 Correct 185 ms 23036 KB Output is correct
4 Correct 172 ms 23160 KB Output is correct
5 Correct 373 ms 23536 KB Output is correct
6 Correct 291 ms 23768 KB Output is correct
7 Correct 288 ms 23804 KB Output is correct
8 Correct 300 ms 23664 KB Output is correct
9 Correct 241 ms 23628 KB Output is correct
10 Correct 267 ms 23672 KB Output is correct
11 Correct 249 ms 23796 KB Output is correct
12 Correct 229 ms 23668 KB Output is correct
13 Correct 231 ms 23540 KB Output is correct
14 Correct 304 ms 23752 KB Output is correct
15 Correct 359 ms 23668 KB Output is correct
16 Correct 302 ms 23796 KB Output is correct
17 Correct 274 ms 23548 KB Output is correct
18 Correct 275 ms 23800 KB Output is correct
19 Correct 294 ms 23672 KB Output is correct
20 Correct 244 ms 23300 KB Output is correct
21 Correct 191 ms 23348 KB Output is correct
22 Correct 197 ms 23288 KB Output is correct
23 Correct 183 ms 23160 KB Output is correct