Submission #114147

#	Time	Username	Problem	Language	Result	Execution time	Memory
114147		popovicirobert	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	451 ms	23804 KiB

railway_trip

#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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55