49802023-04-08 12:30:26zsomborMágikus intervallumcpp17Accepted 100/100206ms11928 KiB
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int n, ansl = 1, ansr = 0;
vector <ll> a(15e4 + 2, 0);
vector <ll> p(15e4 + 2, 0);
vector <ll> v(15e4 + 2, 0);

ll sum(int l, int r) {
    return p[r] - p[l - 1];
}

void get_ans(int l, int r) {
    if (r - l > ansr - ansl) { ansl = l; ansr = r; }
    if (r - l == ansr - ansl && l < ansl) { ansl = l; ansr = r; }
}

void solve(int l, int r) {
    if (r < l) return;
    int m = (l + r) / 2, L, R, M;
    ll mx;

    v[l] = sum(l, m - 1);
    for (int i = l + 1; i <= m; i++) v[i] = min(v[i - 1], sum(i, m - 1));
    mx = -1e15;
    for (int i = m; i <= r; i++) {
        mx = max(mx, a[i]);
        L = l - 1; R = m + 1;
        while (R - L > 1) {
            M = (L + R) / 2;
            (v[M] + sum(m, i) <= 2 * mx ? R = M : L = M);
        }
        if (R < m + 1) get_ans(R, i);
    }

    v[r] = sum(m + 1, r);
    for (int i = r - 1; i >= m; i--) v[i] = min(v[i + 1], sum(m + 1, i));
    mx = -1e15;
    for (int i = m; i >= l; i--) {
        mx = max(mx, a[i]);
        L = m - 1; R = r + 1;
        while (R - L > 1) {
            M = (L + R) / 2;
            (v[M] + sum(i, m) <= 2 * mx ? L = M : R = M);
        }
        if (L > m - 1) get_ans(i, L);
    }

    solve(l, m - 1);
    solve(m + 1, r);
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    solve(1, n);
    cout << ansl << " " << ansr;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms8944 KiB
2Accepted156ms9132 KiB
subtask25/5
3Accepted4ms9088 KiB
4Accepted4ms9344 KiB
5Accepted4ms9560 KiB
6Accepted4ms9844 KiB
7Accepted4ms10056 KiB
8Accepted4ms10196 KiB
subtask310/10
9Accepted4ms10148 KiB
10Accepted4ms10148 KiB
11Accepted6ms10404 KiB
12Accepted4ms10512 KiB
13Accepted4ms10620 KiB
14Accepted4ms10828 KiB
subtask410/10
15Accepted4ms11044 KiB
16Accepted4ms11004 KiB
17Accepted6ms11036 KiB
18Accepted14ms11000 KiB
19Accepted181ms11000 KiB
20Accepted150ms11000 KiB
21Accepted150ms10996 KiB
subtask515/15
22Accepted4ms11044 KiB
23Accepted141ms11300 KiB
24Accepted162ms11252 KiB
subtask660/60
25Accepted165ms11248 KiB
26Accepted185ms11468 KiB
27Accepted184ms11420 KiB
28Accepted179ms11420 KiB
29Accepted179ms11460 KiB
30Accepted177ms11472 KiB
31Accepted206ms11768 KiB
32Accepted203ms11712 KiB
33Accepted153ms11668 KiB
34Accepted153ms11668 KiB
35Accepted153ms11636 KiB
36Accepted181ms11636 KiB
37Accepted145ms11632 KiB
38Accepted150ms11632 KiB
39Accepted4ms11928 KiB