답안 #912714

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
912714	2024-01-19T18:28:46 Z	Acanikolic	Pismo (COCI18_pismo)	C++14	40 / 70	26 ms	6236 KB

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.0 / 70.0

#	결과	실행 시간	메모리	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