42462023-03-18 22:07:04peti1234Mágikus intervallumcpp14Wrong answer 0/10014ms4876 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=1;
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
1Wrong answer14ms1988 KiB
2Wrong answer14ms2296 KiB
subtask20/5
3Wrong answer14ms2612 KiB
4Wrong answer14ms2728 KiB
5Wrong answer14ms3080 KiB
6Wrong answer14ms3012 KiB
7Wrong answer14ms3080 KiB
8Wrong answer14ms3352 KiB
subtask30/10
9Wrong answer14ms3560 KiB
10Wrong answer14ms3412 KiB
11Wrong answer13ms3408 KiB
12Wrong answer13ms3408 KiB
13Wrong answer13ms3416 KiB
14Wrong answer13ms3452 KiB
subtask40/10
15Wrong answer14ms3584 KiB
16Wrong answer14ms3812 KiB
17Wrong answer14ms3772 KiB
18Wrong answer14ms4072 KiB
19Wrong answer13ms3936 KiB
20Wrong answer14ms4188 KiB
21Wrong answer14ms4144 KiB
subtask50/15
22Wrong answer14ms4460 KiB
23Wrong answer14ms4660 KiB
24Wrong answer14ms4508 KiB
subtask60/60
25Wrong answer13ms4452 KiB
26Wrong answer14ms4712 KiB
27Wrong answer14ms4568 KiB
28Wrong answer13ms4572 KiB
29Wrong answer13ms4572 KiB
30Wrong answer13ms4612 KiB
31Wrong answer14ms4616 KiB
32Wrong answer14ms4572 KiB
33Wrong answer14ms4768 KiB
34Wrong answer14ms4620 KiB
35Wrong answer14ms4876 KiB
36Wrong answer14ms4780 KiB
37Wrong answer13ms4784 KiB
38Wrong answer14ms4784 KiB
39Wrong answer14ms4784 KiB