49772023-04-08 12:03:05zsomborMágikus intervallumcpp17Wrong answer 15/100192ms12184 KiB
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int n, ansl, dif = -1;
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 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));
    v[m + 1] = -1e15;
    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) continue;
        if (i - R > dif) { dif = i - R; ansl = R; }
    }

    v[r] = sum(m + 1, r);
    for (int i = r - 1; i >= m; i--) v[i] = min(v[i + 1], sum(m + 1, r));
    v[m - 1] = -1e15;
    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) continue;
        if (L - i > dif) { dif = L - i; ansl = i; }
    }

    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 << " " << ansl + dif;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms8948 KiB
2Accepted152ms9136 KiB
subtask20/5
3Accepted4ms9220 KiB
4Wrong answer4ms9448 KiB
5Wrong answer4ms9660 KiB
6Wrong answer4ms9956 KiB
7Accepted6ms10248 KiB
8Wrong answer4ms10124 KiB
subtask30/10
9Wrong answer6ms10336 KiB
10Wrong answer4ms10592 KiB
11Accepted4ms10468 KiB
12Accepted4ms10464 KiB
13Accepted4ms10468 KiB
14Wrong answer4ms10468 KiB
subtask40/10
15Accepted4ms10720 KiB
16Accepted4ms10936 KiB
17Wrong answer4ms10888 KiB
18Wrong answer14ms10892 KiB
19Wrong answer178ms11144 KiB
20Accepted146ms11360 KiB
21Wrong answer148ms11572 KiB
subtask515/15
22Accepted4ms11528 KiB
23Accepted141ms11784 KiB
24Accepted159ms11816 KiB
subtask60/60
25Accepted164ms11772 KiB
26Accepted180ms11744 KiB
27Accepted180ms11744 KiB
28Accepted172ms11788 KiB
29Accepted167ms11780 KiB
30Accepted168ms11784 KiB
31Accepted192ms11936 KiB
32Accepted192ms11996 KiB
33Accepted150ms11840 KiB
34Accepted149ms11984 KiB
35Wrong answer149ms12184 KiB
36Wrong answer177ms11980 KiB
37Accepted142ms11980 KiB
38Wrong answer146ms11872 KiB
39Wrong answer4ms11872 KiB