4977 2023. 04. 08 12:03:05 zsombor Mágikus intervallum cpp17 Hibás válasz 15/100 192ms 12184 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 8948 KiB
2 Elfogadva 152ms 9136 KiB
subtask2 0/5
3 Elfogadva 4ms 9220 KiB
4 Hibás válasz 4ms 9448 KiB
5 Hibás válasz 4ms 9660 KiB
6 Hibás válasz 4ms 9956 KiB
7 Elfogadva 6ms 10248 KiB
8 Hibás válasz 4ms 10124 KiB
subtask3 0/10
9 Hibás válasz 6ms 10336 KiB
10 Hibás válasz 4ms 10592 KiB
11 Elfogadva 4ms 10468 KiB
12 Elfogadva 4ms 10464 KiB
13 Elfogadva 4ms 10468 KiB
14 Hibás válasz 4ms 10468 KiB
subtask4 0/10
15 Elfogadva 4ms 10720 KiB
16 Elfogadva 4ms 10936 KiB
17 Hibás válasz 4ms 10888 KiB
18 Hibás válasz 14ms 10892 KiB
19 Hibás válasz 178ms 11144 KiB
20 Elfogadva 146ms 11360 KiB
21 Hibás válasz 148ms 11572 KiB
subtask5 15/15
22 Elfogadva 4ms 11528 KiB
23 Elfogadva 141ms 11784 KiB
24 Elfogadva 159ms 11816 KiB
subtask6 0/60
25 Elfogadva 164ms 11772 KiB
26 Elfogadva 180ms 11744 KiB
27 Elfogadva 180ms 11744 KiB
28 Elfogadva 172ms 11788 KiB
29 Elfogadva 167ms 11780 KiB
30 Elfogadva 168ms 11784 KiB
31 Elfogadva 192ms 11936 KiB
32 Elfogadva 192ms 11996 KiB
33 Elfogadva 150ms 11840 KiB
34 Elfogadva 149ms 11984 KiB
35 Hibás válasz 149ms 12184 KiB
36 Hibás válasz 177ms 11980 KiB
37 Elfogadva 142ms 11980 KiB
38 Hibás válasz 146ms 11872 KiB
39 Hibás válasz 4ms 11872 KiB