Submission #801824

#	Time	Username	Problem	Language	Result	Execution time	Memory
801824		vjudge1	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	2060 ms	3252 KiB

railway_trip

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1<<17;

int n, k, Q, arr[N], cnt[N][21], LEFT[N], RIGHT[N];
ll use[N], T, nT;

void solve_subtask3() {
    for(int i = 1; i <= n; ++ i) {
        for(int j = k; j; -- j) {
            cnt[i][j] = cnt[i - 1][j] + (arr[i] <= j);
        }
    }
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k >> Q;

    stack < int > st;

    for(int i = 1; i <= n; ++ i) {
        cin >> arr[i];
        
        for(; !st.empty() && arr[i] >= arr[st.top()]; st.pop());
        LEFT[i] = st.empty() ? 0 : st.top();
        st.push(i);
    }

    for(; !st.empty(); st.pop());

    for(int i = n; i; -- i) {
        for(; !st.empty() && arr[i] >= arr[st.top()]; st.pop());
        RIGHT[i] = st.empty() ? n + 1 : st.top();
        st.push(i);
    }

    queue < int > q;
    for(int a, b; Q --> 0;) {
        cin >> a >> b;
        ++ T;
        use[a] = T;
        q.push(a);
        for(; !q.empty();) {
            int v = q.front();
            q.pop();
            int l = v - 1, r = v + 1, m = 1;
            for(; l && m;) {
                m &= arr[l] < arr[v];
                if(use[l] < T) {
                    use[l] = use[v] + 1;
                    q.push(l);
                }
                l = LEFT[l];
            }
            for(m = 1; r <= n && m;) {
                m &= arr[r] < arr[v];
                if(use[r] < T) {
                    use[r] = use[v] + 1;
                    q.push(r);
                } 
                r = RIGHT[r];
            }
        }
        cout << use[b] - T - 1 << '\n';
        T += n;
    }
}

Compilation message (stderr)

railway_trip.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main() {
      | ^~~~

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