49762023-04-08 11:45:32zsomborMágikus intervallumcpp17Wrong answer 15/100192ms11876 KiB
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int n, ansl, dif = 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 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
1Accepted4ms8820 KiB
2Accepted156ms8996 KiB
subtask20/5
3Wrong answer4ms9352 KiB
4Wrong answer4ms9420 KiB
5Wrong answer4ms9628 KiB
6Wrong answer4ms9584 KiB
7Accepted4ms9716 KiB
8Wrong answer6ms9992 KiB
subtask30/10
9Wrong answer4ms10180 KiB
10Wrong answer6ms10124 KiB
11Accepted6ms10420 KiB
12Accepted6ms10784 KiB
13Accepted6ms10716 KiB
14Wrong answer6ms10716 KiB
subtask40/10
15Wrong answer4ms10760 KiB
16Accepted4ms10940 KiB
17Wrong answer6ms10580 KiB
18Wrong answer14ms10580 KiB
19Wrong answer178ms10580 KiB
20Accepted148ms10840 KiB
21Wrong answer146ms10872 KiB
subtask515/15
22Accepted4ms11004 KiB
23Accepted138ms11152 KiB
24Accepted160ms11028 KiB
subtask60/60
25Accepted165ms10920 KiB
26Accepted180ms11096 KiB
27Accepted180ms11128 KiB
28Accepted168ms11032 KiB
29Accepted168ms11324 KiB
30Accepted170ms11228 KiB
31Accepted192ms11492 KiB
32Accepted190ms11528 KiB
33Accepted149ms11528 KiB
34Accepted149ms11540 KiB
35Wrong answer149ms11408 KiB
36Wrong answer178ms11664 KiB
37Accepted141ms11876 KiB
38Wrong answer146ms11820 KiB
39Wrong answer6ms11824 KiB