Submission #508618

#	Time	Username	Problem	Language	Result	Execution time	Memory
508618		lukameladze	Pismo (COCI18_pismo)	C++14	10 / 70	22 ms	2416 KiB

pismo

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 3e5 + 5;
int t,n,a[N],pr[N],sf[N],cur,le,ri;
int tree[4*N];
void build(int node, int le ,int ri) {
    if (le == ri) {
        tree[node] = a[le];
        return ;
    }
    int mid = (le + ri) / 2;
    build(2*node,le,mid);
    build(2*node + 1, mid + 1, ri);
    tree[node] = min(tree[2*node],tree[2*node + 1]);
}
int getans(int node, int le, int ri, int start,int end) {
    if (le > end || ri < start) {
        return 1e9;
    }
    if (le >= start && ri <= end) {
        return tree[node];
    }
    int mid = (le + ri) / 2;
    return min(getans(2*node,le,mid,start,end), getans(2*node + 1, mid + 1, ri, start,end));
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for (int i = 1; i <= n; i++) {
	    cin>>a[i];
	}
	for (int i = 1; i <= n; i++) {
	    cur = i - 1;
	    while (a[cur] <= a[i] && cur) {
	        cur = pr[cur];
	    }
	    pr[i] = cur;
	}
	for (int i = n; i >= 1; i--) {
	    cur = i +1;
	    while (a[cur] <= a[i] && cur <= n) {
	        cur = sf[cur];
	    }
	    sf[i] = cur;
	}
	build(1,1,n);
	int ans = 1e9;
	for (int i = 1; i <= n ;i++) {
	    le = pr[i] + 1;
	    ri = sf[i] - 1;
	    if (le != ri) ans = min(ans, a[i] - getans(1,1,n,le,ri));
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

pismo.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main() {
      | ^~~~

• Subtask 1: 10 / 70