4247 2023. 03. 18 22:08:29 peti1234 Mágikus intervallum cpp14 Accepted 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
*/
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 3ms 1840 KiB
2 Accepted 71ms 10372 KiB
subtask2 5/5
3 Accepted 3ms 2388 KiB
4 Accepted 3ms 2600 KiB
5 Accepted 3ms 2796 KiB
6 Accepted 3ms 2884 KiB
7 Accepted 3ms 3128 KiB
8 Accepted 3ms 3192 KiB
subtask3 10/10
9 Accepted 3ms 3340 KiB
10 Accepted 3ms 3404 KiB
11 Accepted 3ms 3556 KiB
12 Accepted 3ms 3764 KiB
13 Accepted 3ms 3740 KiB
14 Accepted 3ms 3740 KiB
subtask4 10/10
15 Accepted 2ms 3704 KiB
16 Accepted 3ms 3708 KiB
17 Accepted 3ms 3740 KiB
18 Accepted 8ms 4524 KiB
19 Accepted 70ms 13652 KiB
20 Accepted 43ms 13428 KiB
21 Accepted 48ms 13420 KiB
subtask5 15/15
22 Accepted 2ms 4140 KiB
23 Accepted 93ms 12332 KiB
24 Accepted 108ms 13360 KiB
subtask6 60/60
25 Accepted 71ms 12268 KiB
26 Accepted 82ms 13660 KiB
27 Accepted 83ms 13584 KiB
28 Accepted 70ms 12616 KiB
29 Accepted 68ms 12632 KiB
30 Accepted 71ms 12636 KiB
31 Accepted 79ms 13932 KiB
32 Accepted 82ms 13856 KiB
33 Accepted 68ms 13856 KiB
34 Accepted 57ms 13852 KiB
35 Accepted 67ms 13856 KiB
36 Accepted 70ms 13852 KiB
37 Accepted 43ms 13856 KiB
38 Accepted 41ms 13856 KiB
39 Accepted 3ms 4592 KiB