4247 2023. 03. 18 22:08:29 peti1234 Mágikus intervallum cpp14 Elfogadva 100/100 108ms 13932 KiB
#include <bits/stdc++.h>

using namespace std;
const int c=150005;
long long n, t[c], pref[c], el[c], kov[c], kezd, veg;
bool test=0;
bool solve(int ert) {
    //cout << "solve " << ert << "\n";
    deque<int> q;
    for (int i=1; i<=ert; i++) {
        while (q.size()>0 && t[i]>=t[q.front()]) {
            q.pop_front();
        }
        q.push_front(i);
    }
    if (pref[kov[ert]]<=2*t[q.back()]) {
        kezd=1, veg=kov[ert];
        return true;
    }
    for (int i=ert+1; i<=n; i++) {
        while (q.size()>0 && t[i]>=t[q.front()]) {
            q.pop_front();
        }
        q.push_front(i);
        if (q.back()==i-ert) {
            q.pop_back();
        }
        /*if (ert==3 && i==6) {
            cout << "... " << kov[i] << " " << el[i-ert+1] << "\n";
            cout << pref[kov[i]] << " " <<  pref[el[i-ert+1]] << "\n";
            cout << "... " << q.back() << " " << t[q.back()] << "\n";
        }*/
        if (pref[kov[i]]-pref[el[i-ert+1]]<=2*t[q.back()]) {
            if (ert==3) {
                //cout << "....\n";
            }
            kezd=el[i-ert+1]+1, veg=kov[i];
            return true;
        }
    }
    return false;
}
void trivi() {
    for (int i=1; i<=n; i++) {
        cout << t[i] << " ";
    }
    cout << "\n";
    for (int len=n-1; len>=0; len--) {
        for (int kezd=1; kezd+len<=n; kezd++) {
            veg=kezd+len;
            long long sum=0, maxi=-1e9;
            for (int i=kezd; i<=veg; i++) {
                sum+=t[i];
                maxi=max(maxi, t[i]);
            }
            if (2*maxi>=sum) {
                cout << kezd << " " << veg << "\n";
                return;
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    srand(time(0));
    if (!test) cin >> n;
    else n=400;
    for (int i=1; i<=n; i++) {
        if (!test) cin >> t[i];
        else t[i]=rand()-10000;
        pref[i]=pref[i-1]+t[i];
        el[i]=i-1, kov[i]=i;
    }
    if (test) trivi();
    for (int i=2; i<=n; i++) {
        if (pref[el[i-1]]>=pref[el[i]]) {
            el[i]=el[i-1];
        }
    }
    for (int i=n-1; i>=1; i--) {
        if (pref[kov[i+1]]<=pref[kov[i]]) {
            kov[i]=kov[i+1];
        }
    }
    /*for (int i=1; i<=n; i++) {
        cout << i << " " << el[i] << " " << kov[i] << "\n";
    }*/
    int lo=0, hi=n+1, mid;
    while (hi-lo>1) {
        mid=(hi+lo)/2;
        if (solve(mid)) {
            lo=mid;
        } else {
            hi=mid;
        }
    }
    cout << kezd << " " << veg << "\n";
    return 0;
}
/*
50
5938 21824 22507 24343 2806 13920 3454 2242 12043 26140 11415 6607 17693 2945 15328 19152 32196 17874 2651 26705 1706 4642 20132 1294 17391 12065
19319 7267 14540 29495 7537 14595 25463 18639 5659 29677 4167 17654 18468 24476 26649 3108 10478 13182 15858 31065 27469 19368 24550 15212
*/
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1840 KiB
2 Elfogadva 71ms 10372 KiB
subtask2 5/5
3 Elfogadva 3ms 2388 KiB
4 Elfogadva 3ms 2600 KiB
5 Elfogadva 3ms 2796 KiB
6 Elfogadva 3ms 2884 KiB
7 Elfogadva 3ms 3128 KiB
8 Elfogadva 3ms 3192 KiB
subtask3 10/10
9 Elfogadva 3ms 3340 KiB
10 Elfogadva 3ms 3404 KiB
11 Elfogadva 3ms 3556 KiB
12 Elfogadva 3ms 3764 KiB
13 Elfogadva 3ms 3740 KiB
14 Elfogadva 3ms 3740 KiB
subtask4 10/10
15 Elfogadva 2ms 3704 KiB
16 Elfogadva 3ms 3708 KiB
17 Elfogadva 3ms 3740 KiB
18 Elfogadva 8ms 4524 KiB
19 Elfogadva 70ms 13652 KiB
20 Elfogadva 43ms 13428 KiB
21 Elfogadva 48ms 13420 KiB
subtask5 15/15
22 Elfogadva 2ms 4140 KiB
23 Elfogadva 93ms 12332 KiB
24 Elfogadva 108ms 13360 KiB
subtask6 60/60
25 Elfogadva 71ms 12268 KiB
26 Elfogadva 82ms 13660 KiB
27 Elfogadva 83ms 13584 KiB
28 Elfogadva 70ms 12616 KiB
29 Elfogadva 68ms 12632 KiB
30 Elfogadva 71ms 12636 KiB
31 Elfogadva 79ms 13932 KiB
32 Elfogadva 82ms 13856 KiB
33 Elfogadva 68ms 13856 KiB
34 Elfogadva 57ms 13852 KiB
35 Elfogadva 67ms 13856 KiB
36 Elfogadva 70ms 13852 KiB
37 Elfogadva 43ms 13856 KiB
38 Elfogadva 41ms 13856 KiB
39 Elfogadva 3ms 4592 KiB