Submission #912714

#	Time	Username	Problem	Language	Result	Execution time	Memory
912714		Acanikolic	Pismo (COCI18_pismo)	C++14	40 / 70	26 ms	6236 KiB

pismo

#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 / 70