Submission #169559

#	Time	Username	Problem	Language	Result	Execution time	Memory
169559		combi1k1	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	251 ms	18964 KiB

railway_trip

#include<bits/stdc++.h>

using namespace std;

#define pb  emplace_back

#define X   first
#define Y   second

const int   N   = 1e5 + 1;

int lef[N][20];
int rig[N][20];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int k;  cin >> k;
    int q;  cin >> q;

    vector<int> a(n);

    for(int&x : a)  cin >> x;

    auto build = [&](bool inv)  {
        stack<int>  st;

        for(int i = 0 ; i < n ; ++i)    {
            while (st.size() && a[st.top()] < a[i])
                st.pop();

            if (st.size())  {
                int u = st.top();

                if (inv)    rig[n - i][0] = n - u;
                else        lef[i + 1][0] = u + 1;
            }

            st.push(i);
        }
        reverse(a.begin(),a.end());
    };

    build(0);
    build(1);   rig[n][0] = n;

    for(int i = 0 ; i < 16 ; ++i)
    for(int j = 1 ; j <= n ; ++j)   {
        int x = lef[j][i];
        int y = rig[j][i];

        lef[j][i + 1] = min(lef[x][i],lef[y][i]);
        rig[j][i + 1] = max(rig[x][i],rig[y][i]);
    }

    for(int i = 0 ; i < q ; ++i)    {
        int x;  cin >> x;
        int y;  cin >> y;

        if (x > y)  x ^= (y ^= (x ^= y));

        int ans = 0;

        int l = x;
        int r = x;

        for(int j = 16 ; j >= 0 ; --j)  if (max(rig[l][j],rig[r][j]) < y)   {
            ans += (1 << j);
            int pl = min(lef[l][j],lef[r][j]);
            int pr = max(rig[l][j],rig[r][j]);

            l = pl;
            r = pr;
        }
        x = r;
        l = y;
        r = y;

        for(int j = 16 ; j >= 0 ; --j)  if (min(lef[l][j],lef[r][j]) > x)   {
            ans += (1 << j);
            int pl = min(lef[l][j],lef[r][j]);
            int pr = max(rig[l][j],rig[r][j]);

            l = pl;
            r = pr;
        }

        cout << ans << "\n";
    }
}
/*
9 3 3
3 1 1 1 2 2 2 3 3
2 4
4 9
6 7
*/

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