42472023-03-18 22:08:29peti1234Mágikus intervallumcpp14Elfogadva 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
*/
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1840 KiB
2Elfogadva71ms10372 KiB
subtask25/5
3Elfogadva3ms2388 KiB
4Elfogadva3ms2600 KiB
5Elfogadva3ms2796 KiB
6Elfogadva3ms2884 KiB
7Elfogadva3ms3128 KiB
8Elfogadva3ms3192 KiB
subtask310/10
9Elfogadva3ms3340 KiB
10Elfogadva3ms3404 KiB
11Elfogadva3ms3556 KiB
12Elfogadva3ms3764 KiB
13Elfogadva3ms3740 KiB
14Elfogadva3ms3740 KiB
subtask410/10
15Elfogadva2ms3704 KiB
16Elfogadva3ms3708 KiB
17Elfogadva3ms3740 KiB
18Elfogadva8ms4524 KiB
19Elfogadva70ms13652 KiB
20Elfogadva43ms13428 KiB
21Elfogadva48ms13420 KiB
subtask515/15
22Elfogadva2ms4140 KiB
23Elfogadva93ms12332 KiB
24Elfogadva108ms13360 KiB
subtask660/60
25Elfogadva71ms12268 KiB
26Elfogadva82ms13660 KiB
27Elfogadva83ms13584 KiB
28Elfogadva70ms12616 KiB
29Elfogadva68ms12632 KiB
30Elfogadva71ms12636 KiB
31Elfogadva79ms13932 KiB
32Elfogadva82ms13856 KiB
33Elfogadva68ms13856 KiB
34Elfogadva57ms13852 KiB
35Elfogadva67ms13856 KiB
36Elfogadva70ms13852 KiB
37Elfogadva43ms13856 KiB
38Elfogadva41ms13856 KiB
39Elfogadva3ms4592 KiB