Submission #1307557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307557		florescent	Railway Trip (JOI17_railway_trip)	C++20	0 / 100	74 ms	17904 KiB

railway_trip

//STRIKER!
#include <iostream> 
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <iomanip>
#include <numeric>
#include <random>
#include <chrono>

using namespace std;
//#define int int64_t //uint64_t
#define pb push_back
#define perfectblue cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
#define all(a) a.begin(), a.end()
#define sz(a) ((int)a.size())

const int maxn = 2e5 + 10;
const int LOG = 19;
int n, k, q;
int a[maxn];
int L[maxn];
int R[maxn];
int spl[LOG + 1][maxn];
int spr[LOG + 1][maxn];

void sol() {
    cin >> n >> k >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() and a[st.top()] < a[i]) {
            st.pop();
        }
        L[i] = (!st.empty() ? st.top() : i);
        st.push(i);
    }
    while (!st.empty()) {
        st.pop();
    }
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() and a[st.top()] < a[i]) {
            st.pop();
        }
        R[i] = (!st.empty() ? st.top() : i);
        st.push(i);
    }

    for (int i = 0; i < n; i++) {
        spl[0][i] = L[i];
        spr[0][i] = R[i];
    }

    for (int k = 1; k <= LOG; k++) {
        for (int i = 0; i < n; i++) {
            int l = spl[k - 1][i];
            int r = spr[k - 1][i];
            spl[k][i] = min(spl[k - 1][l], spl[k - 1][r]);
            spr[k][i] = max(spr[k - 1][l], spr[k - 1][r]);
        }
    }

    while (q--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (a > b) {
            swap(a, b);
        }

        int l = a;
        int r = a;
        int ans = 0;

        for (int k = LOG; k >= 0; k--) {
            if (max(spr[k][l], spr[k][r]) < b) {
                ans += (1 << k);
                int ll = l;
                int rr = r;
                l = min(spl[k][ll], spl[k][rr]);
                r = max(spr[k][ll], spr[k][rr]);
            }
        }

        a = r;
        l = b;
        r = b;

        for (int k = LOG; k >= 0; k--) {
            if (max(spl[k][l], spl[k][r]) > a) {
                ans += (1 << k);
                int ll = l;
                int rr = r;
                l = min(spl[k][ll], spl[k][rr]);
                r = max(spr[k][ll], spr[k][rr]);
            }
        }

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

int32_t main() {
    perfectblue;
    int t = 1;
    //cin >> t;

    while (t--) {
        sol();
    }

    return 0;
}

//freopen("name", "r", stdin);
//freopen("name", "w", stdout);

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55