oj.uz

Submission #293158

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Incorrect 1 ms 1152 KB Output isn't correct
5 Incorrect 55 ms 17280 KB Output isn't correct
6 Correct 54 ms 17280 KB Output is correct
7 Correct 54 ms 17280 KB Output is correct