oj.uz

Submission #912707

# Submission time Handle Problem Language Result Execution time Memory
912707 2024-01-19T18:21:03 Z Acanikolic Pismo (COCI18_pismo) C++14
0 / 70
 17 ms 5460 KB 
#include <bits/stdc++.h>

#define int long long

#define pb push_back

#define F first

#define S second

using namespace std;

const int N = 2e5 + 10;

const int inf = 1e18;

int mn[N * 4],a[N];

void build(int node,int tl,int tr) {
    if(tl == tr) {
        mn[node] = a[tl];
        return;
    }
    int mid = (tl + tr) / 2;
    build(node * 2,tl,mid);
    build(node * 2 + 1,mid + 1,tr);
    mn[node] = min(mn[node * 2],mn[node * 2 + 1]);
}

int get(int node,int tl,int tr,int l,int r) {
    if(tl > r || tr < l) return inf;
    if(tl >= l && tr <= r) return mn[node];
    int mid = (tl + tr) / 2;
    return min(get(node * 2,tl,mid,l,r),get(node * 2 + 1,mid + 1,tr,l,r));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<int>veci(n + 1,-1);
    stack<int>st;
    for(int i = 1; i <= n; i++) {
        while(st.size() && a[st.top()] <= a[i]) st.pop();
        if(st.size()) veci[i] = st.top();
        st.push(i);
    }
    build(1,1,n);
    int res = inf;
    for(int i = 1; i <= n; i++) {
        int l = 1;
        if(veci[i] != -1) l = veci[i] + 1 ;
        if(l >= i - 1) continue;
        res = min(res,a[i] - get(1,1,n,l,i - 1));
    }
    cout << res;
    return 0;
}

Subtask #1
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Incorrect 2 ms 2616 KB Output isn't correct
5 Incorrect 17 ms 5460 KB Output isn't correct
6 Incorrect 15 ms 5212 KB Output isn't correct
7 Incorrect 14 ms 5212 KB Output isn't correct