oj.uz

Submission #971029

# Submission time Handle Problem Language Result Execution time Memory
971029 2024-04-27T20:36:07 Z RandomUser Pismo (COCI18_pismo) C++17
0 / 70
 39 ms 18772 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Runtime error 3 ms 4700 KB Execution killed with signal 11
3 Incorrect 1 ms 2496 KB Output isn't correct
4 Runtime error 3 ms 4696 KB Execution killed with signal 11
5 Incorrect 39 ms 9996 KB Output isn't correct
6 Runtime error 37 ms 18772 KB Execution killed with signal 11
7 Incorrect 31 ms 10004 KB Output isn't correct