49782023-04-08 12:15:04zsomborMágikus intervallumcpp17Hibás válasz 15/100197ms11628 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms8816 KiB
2Elfogadva152ms9108 KiB
subtask20/5
3Elfogadva4ms9684 KiB
4Hibás válasz4ms9836 KiB
5Elfogadva4ms10044 KiB
6Hibás válasz4ms10140 KiB
7Elfogadva6ms10244 KiB
8Hibás válasz6ms10456 KiB
subtask30/10
9Elfogadva4ms10536 KiB
10Hibás válasz4ms10680 KiB
11Elfogadva6ms10968 KiB
12Elfogadva4ms10924 KiB
13Elfogadva6ms10880 KiB
14Hibás válasz6ms10880 KiB
subtask40/10
15Elfogadva4ms10844 KiB
16Elfogadva4ms11096 KiB
17Elfogadva6ms11040 KiB
18Hibás válasz13ms11040 KiB
19Hibás válasz178ms11332 KiB
20Elfogadva149ms11284 KiB
21Hibás válasz149ms11304 KiB
subtask515/15
22Elfogadva4ms11304 KiB
23Elfogadva138ms11292 KiB
24Elfogadva160ms11296 KiB
subtask60/60
25Elfogadva164ms11164 KiB
26Elfogadva181ms11196 KiB
27Elfogadva180ms11240 KiB
28Elfogadva177ms11228 KiB
29Elfogadva173ms11496 KiB
30Elfogadva172ms11408 KiB
31Elfogadva197ms11372 KiB
32Elfogadva195ms11372 KiB
33Elfogadva151ms11416 KiB
34Elfogadva150ms11412 KiB
35Hibás válasz150ms11380 KiB
36Hibás válasz179ms11420 KiB
37Elfogadva143ms11420 KiB
38Hibás válasz148ms11452 KiB
39Hibás válasz6ms11628 KiB