42472023-03-18 22:08:29peti1234Mágikus intervallumcpp14Accepted 100/100108ms13932 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
*/
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1840 KiB
2Accepted71ms10372 KiB
subtask25/5
3Accepted3ms2388 KiB
4Accepted3ms2600 KiB
5Accepted3ms2796 KiB
6Accepted3ms2884 KiB
7Accepted3ms3128 KiB
8Accepted3ms3192 KiB
subtask310/10
9Accepted3ms3340 KiB
10Accepted3ms3404 KiB
11Accepted3ms3556 KiB
12Accepted3ms3764 KiB
13Accepted3ms3740 KiB
14Accepted3ms3740 KiB
subtask410/10
15Accepted2ms3704 KiB
16Accepted3ms3708 KiB
17Accepted3ms3740 KiB
18Accepted8ms4524 KiB
19Accepted70ms13652 KiB
20Accepted43ms13428 KiB
21Accepted48ms13420 KiB
subtask515/15
22Accepted2ms4140 KiB
23Accepted93ms12332 KiB
24Accepted108ms13360 KiB
subtask660/60
25Accepted71ms12268 KiB
26Accepted82ms13660 KiB
27Accepted83ms13584 KiB
28Accepted70ms12616 KiB
29Accepted68ms12632 KiB
30Accepted71ms12636 KiB
31Accepted79ms13932 KiB
32Accepted82ms13856 KiB
33Accepted68ms13856 KiB
34Accepted57ms13852 KiB
35Accepted67ms13856 KiB
36Accepted70ms13852 KiB
37Accepted43ms13856 KiB
38Accepted41ms13856 KiB
39Accepted3ms4592 KiB