4976 2023. 04. 08 11:45:32 zsombor Mágikus intervallum cpp17 Hibás válasz 15/100 192ms 11876 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 8820 KiB
2 Elfogadva 156ms 8996 KiB
subtask2 0/5
3 Hibás válasz 4ms 9352 KiB
4 Hibás válasz 4ms 9420 KiB
5 Hibás válasz 4ms 9628 KiB
6 Hibás válasz 4ms 9584 KiB
7 Elfogadva 4ms 9716 KiB
8 Hibás válasz 6ms 9992 KiB
subtask3 0/10
9 Hibás válasz 4ms 10180 KiB
10 Hibás válasz 6ms 10124 KiB
11 Elfogadva 6ms 10420 KiB
12 Elfogadva 6ms 10784 KiB
13 Elfogadva 6ms 10716 KiB
14 Hibás válasz 6ms 10716 KiB
subtask4 0/10
15 Hibás válasz 4ms 10760 KiB
16 Elfogadva 4ms 10940 KiB
17 Hibás válasz 6ms 10580 KiB
18 Hibás válasz 14ms 10580 KiB
19 Hibás válasz 178ms 10580 KiB
20 Elfogadva 148ms 10840 KiB
21 Hibás válasz 146ms 10872 KiB
subtask5 15/15
22 Elfogadva 4ms 11004 KiB
23 Elfogadva 138ms 11152 KiB
24 Elfogadva 160ms 11028 KiB
subtask6 0/60
25 Elfogadva 165ms 10920 KiB
26 Elfogadva 180ms 11096 KiB
27 Elfogadva 180ms 11128 KiB
28 Elfogadva 168ms 11032 KiB
29 Elfogadva 168ms 11324 KiB
30 Elfogadva 170ms 11228 KiB
31 Elfogadva 192ms 11492 KiB
32 Elfogadva 190ms 11528 KiB
33 Elfogadva 149ms 11528 KiB
34 Elfogadva 149ms 11540 KiB
35 Hibás válasz 149ms 11408 KiB
36 Hibás válasz 178ms 11664 KiB
37 Elfogadva 141ms 11876 KiB
38 Hibás válasz 146ms 11820 KiB
39 Hibás válasz 6ms 11824 KiB