Submission #971029

#	Time	Username	Problem	Language	Result	Execution time	Memory
971029		RandomUser	Pismo (COCI18_pismo)	C++17	0 / 70	39 ms	18772 KiB

pismo

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;

int log_dp[maxn+1], table[maxn+1][20], v[maxn+1], L[maxn+1], R[maxn+1];

int query(int l, int r) {
    int k = log_dp[r-l+1];
    return max(table[l][k], table[r-(1<<k)+1][k]);
}

int main() {
    int n, ans = 0;
    cin >> n;

    for(int i=2; i<=n; i++) log_dp[i] = log_dp[i/2] + 1;
    for(int i=0; i<n; i++) cin >> v[i], table[i][0] = v[i];

    for(int j=1; j<20; j++)
        for(int i=0; i+(1<<j)-1<n; i++) table[i][j] = max(table[i][j-1], table[i+(1<<(j-1))][j-1]);

    stack<pair<int, int> > st;
    st.push({ -1, -1 });

    for(int i=0; i<n; i++) {
        while(!st.empty() && st.top().second >= v[i]) st.pop();
        L[i] = st.top().first + 1;
        st.push({ i, v[i] });
    }

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

    st.push({ n, -1 });
    for(int i=n-1; i>=0; i--) {
        while(!st.empty() && st.top().second >= v[i]) st.pop();
        R[i] = st.top().first - 1;
        st.push({ i, v[i] });
    }

    for(int i=0; i<n; i++) ans = max(ans, query(L[i], R[i]) - v[i]);
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 0 / 70