# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
912702 | Acanikolic | Pismo (COCI18_pismo) | C++14 | 17 ms | 5248 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(l > r) return -inf;
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 ;
res = min(res,a[i] - get(1,1,n,l,i - 1));
}
cout << res;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |