Submission #199822

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
199822	2020-02-03T14:35:32 Z	ahmad_salah	Pismo (COCI18_pismo)	C++14	70 / 70	49 ms	5112 KB

pismo

#include <bits/stdc++.h>

using namespace std;

const int M = 1e5;
int n, arr[M];
pair<int, int> segMin[4 * M], segMax[4 * M];

pair<int, int> buildMin(int l, int r, int i) {
    if (l == r)
        segMin[i] = {arr[l], l};
    else
        segMin[i] = min(buildMin(l, (l + r) / 2, i * 2 + 1), buildMin((l + r) / 2 + 1, r, i * 2 + 2));
    return segMin[i];
}

pair<int, int> Min(int l, int r, int L, int R, int i) {
    if (L >= l && R <= r)
        return segMin[i];
    if (L > r || R < l)
        return {2e9, 2e9};
    return min(Min(l, r, L, (L + R) / 2, i * 2 + 1), Min(l, r, (L + R) / 2 + 1, R, i * 2 + 2));
}

pair<int, int> buildMax(int l, int r, int i) {
    if (l == r)
        segMax[i] = {arr[l], l};
    else
        segMax[i] = max(buildMax(l, (l + r) / 2, i * 2 + 1), buildMax((l + r) / 2 + 1, r, i * 2 + 2));
    return segMax[i];
}

pair<int, int> Max(int l, int r, int L, int R, int i) {
    if (L >= l && R <= r)
        return segMax[i];
    if (L > r || R < l)
        return {-2e9, -2e9};
    return max(Max(l, r, L, (L + R) / 2, i * 2 + 1), Max(l, r, (L + R) / 2 + 1, R, i * 2 + 2));
}

int solve(int l, int r) {
    if (r >= n || l < 0 || r - l < 1)
        return 2e9;
    pair<int, int> L, R;
    L = Min(l, r, 0, n - 1, 0);
    R = Max(l, r, 0, n - 1, 0);
    if (L.second > R.second)
        swap(L, R);

    return min(abs(R.first - L.first), min(solve(l, L.second - 1), min(solve(L.second + 1, R.second - 1), solve(R.second + 1, r))));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int ans = 2e9;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> arr[i];
    buildMax(0, n - 1, 0);
    buildMin(0, n - 1, 0);

    for (int i = 1; i < n; i++)
        ans = min(ans, abs(arr[i] - arr[i - 1]));

    cout << min(ans, solve(0, n - 1)) << '\n';

    return 0;
}

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	504 KB	Output is correct
4	Correct	6 ms	504 KB	Output is correct
5	Correct	42 ms	4856 KB	Output is correct
6	Correct	49 ms	5112 KB	Output is correct
7	Correct	43 ms	4984 KB	Output is correct