Submission #293159

#	Time	Username	Problem	Language	Result	Execution time	Memory
293159		7_7_7	Pismo (COCI18_pismo)	C++17	50 / 70	75 ms	32384 KiB

pismo

#include <bits/stdc++.h>

using namespace std;

const long long M = 21;
const long long N = 1e5 + 7;

long long n;
long long lg[N];
long long mn[N][M];
long long mx[N][M];
pair<long long, long long> a[N];
pair<long long, long long> get(long long l, long long r){
    if(l > r) swap(l, r);
    long long h = lg[(r - l + 1)];
    long long _mn = min(mn[l][h], mn[r - (1 << h) + 1][h]);
    long long _mx = max(mx[l][h], mx[r - (1 << h) + 1][h]);
    return {_mn, _mx};
}
int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n;
    for(long long i = 1; i <= n; i ++){
        cin >> a[i].first;
        a[i].second = i;
        mx[i][0] = a[i].first;
        mn[i][0] = a[i].first;
    }
    for(long long i = 2; i < N; i ++) lg[i] = lg[i / 2] + 1;

    for(long long j = 1; j < M; j ++){
        for(long long i = 1; i + (1 << j) - 1 <= n; i ++){
            mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
            mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
        }
    }
    sort(a + 1, a + n + 1);
    long long res = LLONG_MAX;
    for(long long i = 2; i <= n; i ++){
        pair<long long, long long> ans = get(a[i - 1].second, a[i].second);
        res = min(res, ans.second - ans.first);
    }
    cout << res << "\n";
}

• Subtask 1: 50 / 70