oj.uz

Submission #912714

# Submission time Handle Problem Language Result Execution time Memory
912714 2024-01-19T18:28:46 Z Acanikolic Pismo (COCI18_pismo) C++14
40 / 70
 26 ms 6236 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);
    }
    while(st.size()) st.pop();
    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;
        //cout << l << " " << i - 1 << " " << get(1,1,n,l,i - 1) << endl;
        res = min(res,a[i] - get(1,1,n,l,i - 1));
    }
    reverse(a + 1,a + n + 1);
    for(int i = 1; i <= n; i++) {
        veci[i] = -1;
        while(st.size() && a[st.top()] <= a[i]) st.pop();
        if(st.size()) veci[i] = st.top();
        st.push(i);
    }
    build(1,1,n);
    for(int i = 1; i <= n; i++) {
        int l = 1;
        if(veci[i] != -1) l = veci[i] + 1 ;
        if(l > i - 1) continue;
        //cout << l << " " << i - 1 << " " << get(1,1,n,l,i - 1) << endl;
        res = min(res,a[i] - get(1,1,n,l,i - 1));
    }
    cout << res;
    return 0;
}

Subtask #1
40.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Correct 25 ms 6132 KB Output is correct
6 Correct 25 ms 6236 KB Output is correct
7 Correct 26 ms 6236 KB Output is correct