49772023-04-08 12:03:05zsomborMágikus intervallumcpp17Hibás válasz 15/100192ms12184 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms8948 KiB
2Elfogadva152ms9136 KiB
subtask20/5
3Elfogadva4ms9220 KiB
4Hibás válasz4ms9448 KiB
5Hibás válasz4ms9660 KiB
6Hibás válasz4ms9956 KiB
7Elfogadva6ms10248 KiB
8Hibás válasz4ms10124 KiB
subtask30/10
9Hibás válasz6ms10336 KiB
10Hibás válasz4ms10592 KiB
11Elfogadva4ms10468 KiB
12Elfogadva4ms10464 KiB
13Elfogadva4ms10468 KiB
14Hibás válasz4ms10468 KiB
subtask40/10
15Elfogadva4ms10720 KiB
16Elfogadva4ms10936 KiB
17Hibás válasz4ms10888 KiB
18Hibás válasz14ms10892 KiB
19Hibás válasz178ms11144 KiB
20Elfogadva146ms11360 KiB
21Hibás válasz148ms11572 KiB
subtask515/15
22Elfogadva4ms11528 KiB
23Elfogadva141ms11784 KiB
24Elfogadva159ms11816 KiB
subtask60/60
25Elfogadva164ms11772 KiB
26Elfogadva180ms11744 KiB
27Elfogadva180ms11744 KiB
28Elfogadva172ms11788 KiB
29Elfogadva167ms11780 KiB
30Elfogadva168ms11784 KiB
31Elfogadva192ms11936 KiB
32Elfogadva192ms11996 KiB
33Elfogadva150ms11840 KiB
34Elfogadva149ms11984 KiB
35Hibás válasz149ms12184 KiB
36Hibás válasz177ms11980 KiB
37Elfogadva142ms11980 KiB
38Hibás válasz146ms11872 KiB
39Hibás válasz4ms11872 KiB