Submission #199822

#	Time	Username	Problem	Language	Result	Execution time	Memory
199822		ahmad_salah	Pismo (COCI18_pismo)	C++14	70 / 70	49 ms	5112 KiB

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 / 70