4980 2023. 04. 08 12:30:26 zsombor Mágikus intervallum cpp17 Elfogadva 100/100 206ms 11928 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 8944 KiB
2 Elfogadva 156ms 9132 KiB
subtask2 5/5
3 Elfogadva 4ms 9088 KiB
4 Elfogadva 4ms 9344 KiB
5 Elfogadva 4ms 9560 KiB
6 Elfogadva 4ms 9844 KiB
7 Elfogadva 4ms 10056 KiB
8 Elfogadva 4ms 10196 KiB
subtask3 10/10
9 Elfogadva 4ms 10148 KiB
10 Elfogadva 4ms 10148 KiB
11 Elfogadva 6ms 10404 KiB
12 Elfogadva 4ms 10512 KiB
13 Elfogadva 4ms 10620 KiB
14 Elfogadva 4ms 10828 KiB
subtask4 10/10
15 Elfogadva 4ms 11044 KiB
16 Elfogadva 4ms 11004 KiB
17 Elfogadva 6ms 11036 KiB
18 Elfogadva 14ms 11000 KiB
19 Elfogadva 181ms 11000 KiB
20 Elfogadva 150ms 11000 KiB
21 Elfogadva 150ms 10996 KiB
subtask5 15/15
22 Elfogadva 4ms 11044 KiB
23 Elfogadva 141ms 11300 KiB
24 Elfogadva 162ms 11252 KiB
subtask6 60/60
25 Elfogadva 165ms 11248 KiB
26 Elfogadva 185ms 11468 KiB
27 Elfogadva 184ms 11420 KiB
28 Elfogadva 179ms 11420 KiB
29 Elfogadva 179ms 11460 KiB
30 Elfogadva 177ms 11472 KiB
31 Elfogadva 206ms 11768 KiB
32 Elfogadva 203ms 11712 KiB
33 Elfogadva 153ms 11668 KiB
34 Elfogadva 153ms 11668 KiB
35 Elfogadva 153ms 11636 KiB
36 Elfogadva 181ms 11636 KiB
37 Elfogadva 145ms 11632 KiB
38 Elfogadva 150ms 11632 KiB
39 Elfogadva 4ms 11928 KiB