oj.uz

Submission #169558

# Submission time Handle Problem Language Result Execution time Memory
169558 2019-12-21T05:06:21 Z combi1k1 Railway Trip (JOI17_railway_trip) C++14
0 / 100
 133 ms 18476 KB 
#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);

    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 42 ms 16588 KB Output is correct
3 Correct 42 ms 16632 KB Output is correct
4 Correct 41 ms 16632 KB Output is correct
5 Correct 42 ms 16648 KB Output is correct
6 Correct 42 ms 16888 KB Output is correct
7 Incorrect 45 ms 17044 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 18388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 18476 KB Output isn't correct
2 Halted 0 ms 0 KB -