49782023-04-08 12:15:04zsomborMágikus intervallumcpp17Wrong answer 15/100197ms11628 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));
    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) 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, 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) 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
1Accepted4ms8816 KiB
2Accepted152ms9108 KiB
subtask20/5
3Accepted4ms9684 KiB
4Wrong answer4ms9836 KiB
5Accepted4ms10044 KiB
6Wrong answer4ms10140 KiB
7Accepted6ms10244 KiB
8Wrong answer6ms10456 KiB
subtask30/10
9Accepted4ms10536 KiB
10Wrong answer4ms10680 KiB
11Accepted6ms10968 KiB
12Accepted4ms10924 KiB
13Accepted6ms10880 KiB
14Wrong answer6ms10880 KiB
subtask40/10
15Accepted4ms10844 KiB
16Accepted4ms11096 KiB
17Accepted6ms11040 KiB
18Wrong answer13ms11040 KiB
19Wrong answer178ms11332 KiB
20Accepted149ms11284 KiB
21Wrong answer149ms11304 KiB
subtask515/15
22Accepted4ms11304 KiB
23Accepted138ms11292 KiB
24Accepted160ms11296 KiB
subtask60/60
25Accepted164ms11164 KiB
26Accepted181ms11196 KiB
27Accepted180ms11240 KiB
28Accepted177ms11228 KiB
29Accepted173ms11496 KiB
30Accepted172ms11408 KiB
31Accepted197ms11372 KiB
32Accepted195ms11372 KiB
33Accepted151ms11416 KiB
34Accepted150ms11412 KiB
35Wrong answer150ms11380 KiB
36Wrong answer179ms11420 KiB
37Accepted143ms11420 KiB
38Wrong answer148ms11452 KiB
39Wrong answer6ms11628 KiB