oj.uz

Submission #293159

# Submission time Handle Problem Language Result Execution time Memory
293159 2020-09-07T17:09:39 Z 7_7_7 Pismo (COCI18_pismo) C++17
50 / 70
 75 ms 32384 KB 
#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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 2 ms 1920 KB Output is correct
4 Incorrect 2 ms 1792 KB Output isn't correct
5 Incorrect 75 ms 32376 KB Output isn't correct
6 Correct 71 ms 32376 KB Output is correct
7 Correct 71 ms 32384 KB Output is correct