Submission #293158

#	Time	Username	Problem	Language	Result	Execution time	Memory
293158		7_7_7	Pismo (COCI18_pismo)	C++17	50 / 70	55 ms	17280 KiB

pismo

#include <bits/stdc++.h>

using namespace std;

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

int n;
int lg[N];
int mn[N][M];
int mx[N][M];
pair<int, int> a[N];
pair<int, int> get(int l, int r){
    if(l > r) swap(l, r);
    int h = lg[(r - l + 1)];
    int _mn = min(mn[l][h], mn[r - (1 << h) + 1][h]);
    int _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(int 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(int i = 2; i < N; i ++) lg[i] = lg[i / 2] + 1;

    for(int j = 1; j < M; j ++){
        for(int 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]);
        }
    }
    int res = INT_MAX;
    sort(a + 1, a + n + 1);
    for(int i = 2; i <= n; i ++){
        pair<int, int> ans = get(a[i - 1].second, a[i].second);
        res = min(res, ans.second - ans.first);
    }
    cout << res << "\n";
}

• Subtask 1: 50 / 70