49762023-04-08 11:45:32zsomborMágikus intervallumcpp17Hibás válasz 15/100192ms11876 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms8820 KiB
2Elfogadva156ms8996 KiB
subtask20/5
3Hibás válasz4ms9352 KiB
4Hibás válasz4ms9420 KiB
5Hibás válasz4ms9628 KiB
6Hibás válasz4ms9584 KiB
7Elfogadva4ms9716 KiB
8Hibás válasz6ms9992 KiB
subtask30/10
9Hibás válasz4ms10180 KiB
10Hibás válasz6ms10124 KiB
11Elfogadva6ms10420 KiB
12Elfogadva6ms10784 KiB
13Elfogadva6ms10716 KiB
14Hibás válasz6ms10716 KiB
subtask40/10
15Hibás válasz4ms10760 KiB
16Elfogadva4ms10940 KiB
17Hibás válasz6ms10580 KiB
18Hibás válasz14ms10580 KiB
19Hibás válasz178ms10580 KiB
20Elfogadva148ms10840 KiB
21Hibás válasz146ms10872 KiB
subtask515/15
22Elfogadva4ms11004 KiB
23Elfogadva138ms11152 KiB
24Elfogadva160ms11028 KiB
subtask60/60
25Elfogadva165ms10920 KiB
26Elfogadva180ms11096 KiB
27Elfogadva180ms11128 KiB
28Elfogadva168ms11032 KiB
29Elfogadva168ms11324 KiB
30Elfogadva170ms11228 KiB
31Elfogadva192ms11492 KiB
32Elfogadva190ms11528 KiB
33Elfogadva149ms11528 KiB
34Elfogadva149ms11540 KiB
35Hibás válasz149ms11408 KiB
36Hibás válasz178ms11664 KiB
37Elfogadva141ms11876 KiB
38Hibás válasz146ms11820 KiB
39Hibás válasz6ms11824 KiB