4978 2023. 04. 08 12:15:04 zsombor Mágikus intervallum cpp17 Hibás válasz 15/100 197ms 11628 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 8816 KiB
2 Elfogadva 152ms 9108 KiB
subtask2 0/5
3 Elfogadva 4ms 9684 KiB
4 Hibás válasz 4ms 9836 KiB
5 Elfogadva 4ms 10044 KiB
6 Hibás válasz 4ms 10140 KiB
7 Elfogadva 6ms 10244 KiB
8 Hibás válasz 6ms 10456 KiB
subtask3 0/10
9 Elfogadva 4ms 10536 KiB
10 Hibás válasz 4ms 10680 KiB
11 Elfogadva 6ms 10968 KiB
12 Elfogadva 4ms 10924 KiB
13 Elfogadva 6ms 10880 KiB
14 Hibás válasz 6ms 10880 KiB
subtask4 0/10
15 Elfogadva 4ms 10844 KiB
16 Elfogadva 4ms 11096 KiB
17 Elfogadva 6ms 11040 KiB
18 Hibás válasz 13ms 11040 KiB
19 Hibás válasz 178ms 11332 KiB
20 Elfogadva 149ms 11284 KiB
21 Hibás válasz 149ms 11304 KiB
subtask5 15/15
22 Elfogadva 4ms 11304 KiB
23 Elfogadva 138ms 11292 KiB
24 Elfogadva 160ms 11296 KiB
subtask6 0/60
25 Elfogadva 164ms 11164 KiB
26 Elfogadva 181ms 11196 KiB
27 Elfogadva 180ms 11240 KiB
28 Elfogadva 177ms 11228 KiB
29 Elfogadva 173ms 11496 KiB
30 Elfogadva 172ms 11408 KiB
31 Elfogadva 197ms 11372 KiB
32 Elfogadva 195ms 11372 KiB
33 Elfogadva 151ms 11416 KiB
34 Elfogadva 150ms 11412 KiB
35 Hibás válasz 150ms 11380 KiB
36 Hibás válasz 179ms 11420 KiB
37 Elfogadva 143ms 11420 KiB
38 Hibás válasz 148ms 11452 KiB
39 Hibás válasz 6ms 11628 KiB