42462023-03-18 22:07:04peti1234Mágikus intervallumcpp14Hibás válasz 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
*/
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz14ms1988 KiB
2Hibás válasz14ms2296 KiB
subtask20/5
3Hibás válasz14ms2612 KiB
4Hibás válasz14ms2728 KiB
5Hibás válasz14ms3080 KiB
6Hibás válasz14ms3012 KiB
7Hibás válasz14ms3080 KiB
8Hibás válasz14ms3352 KiB
subtask30/10
9Hibás válasz14ms3560 KiB
10Hibás válasz14ms3412 KiB
11Hibás válasz13ms3408 KiB
12Hibás válasz13ms3408 KiB
13Hibás válasz13ms3416 KiB
14Hibás válasz13ms3452 KiB
subtask40/10
15Hibás válasz14ms3584 KiB
16Hibás válasz14ms3812 KiB
17Hibás válasz14ms3772 KiB
18Hibás válasz14ms4072 KiB
19Hibás válasz13ms3936 KiB
20Hibás válasz14ms4188 KiB
21Hibás válasz14ms4144 KiB
subtask50/15
22Hibás válasz14ms4460 KiB
23Hibás válasz14ms4660 KiB
24Hibás válasz14ms4508 KiB
subtask60/60
25Hibás válasz13ms4452 KiB
26Hibás válasz14ms4712 KiB
27Hibás válasz14ms4568 KiB
28Hibás válasz13ms4572 KiB
29Hibás válasz13ms4572 KiB
30Hibás válasz13ms4612 KiB
31Hibás válasz14ms4616 KiB
32Hibás válasz14ms4572 KiB
33Hibás válasz14ms4768 KiB
34Hibás válasz14ms4620 KiB
35Hibás válasz14ms4876 KiB
36Hibás válasz14ms4780 KiB
37Hibás válasz13ms4784 KiB
38Hibás válasz14ms4784 KiB
39Hibás válasz14ms4784 KiB