49802023-04-08 12:30:26zsomborMágikus intervallumcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms8944 KiB
2Elfogadva156ms9132 KiB
subtask25/5
3Elfogadva4ms9088 KiB
4Elfogadva4ms9344 KiB
5Elfogadva4ms9560 KiB
6Elfogadva4ms9844 KiB
7Elfogadva4ms10056 KiB
8Elfogadva4ms10196 KiB
subtask310/10
9Elfogadva4ms10148 KiB
10Elfogadva4ms10148 KiB
11Elfogadva6ms10404 KiB
12Elfogadva4ms10512 KiB
13Elfogadva4ms10620 KiB
14Elfogadva4ms10828 KiB
subtask410/10
15Elfogadva4ms11044 KiB
16Elfogadva4ms11004 KiB
17Elfogadva6ms11036 KiB
18Elfogadva14ms11000 KiB
19Elfogadva181ms11000 KiB
20Elfogadva150ms11000 KiB
21Elfogadva150ms10996 KiB
subtask515/15
22Elfogadva4ms11044 KiB
23Elfogadva141ms11300 KiB
24Elfogadva162ms11252 KiB
subtask660/60
25Elfogadva165ms11248 KiB
26Elfogadva185ms11468 KiB
27Elfogadva184ms11420 KiB
28Elfogadva179ms11420 KiB
29Elfogadva179ms11460 KiB
30Elfogadva177ms11472 KiB
31Elfogadva206ms11768 KiB
32Elfogadva203ms11712 KiB
33Elfogadva153ms11668 KiB
34Elfogadva153ms11668 KiB
35Elfogadva153ms11636 KiB
36Elfogadva181ms11636 KiB
37Elfogadva145ms11632 KiB
38Elfogadva150ms11632 KiB
39Elfogadva4ms11928 KiB