4246 2023. 03. 18 22:07:04 peti1234 Mágikus intervallum cpp14 Rossz válasz 0/100 14ms 4876 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Rossz válasz 14ms 1988 KiB
2 Rossz válasz 14ms 2296 KiB
subtask2 0/5
3 Rossz válasz 14ms 2612 KiB
4 Rossz válasz 14ms 2728 KiB
5 Rossz válasz 14ms 3080 KiB
6 Rossz válasz 14ms 3012 KiB
7 Rossz válasz 14ms 3080 KiB
8 Rossz válasz 14ms 3352 KiB
subtask3 0/10
9 Rossz válasz 14ms 3560 KiB
10 Rossz válasz 14ms 3412 KiB
11 Rossz válasz 13ms 3408 KiB
12 Rossz válasz 13ms 3408 KiB
13 Rossz válasz 13ms 3416 KiB
14 Rossz válasz 13ms 3452 KiB
subtask4 0/10
15 Rossz válasz 14ms 3584 KiB
16 Rossz válasz 14ms 3812 KiB
17 Rossz válasz 14ms 3772 KiB
18 Rossz válasz 14ms 4072 KiB
19 Rossz válasz 13ms 3936 KiB
20 Rossz válasz 14ms 4188 KiB
21 Rossz válasz 14ms 4144 KiB
subtask5 0/15
22 Rossz válasz 14ms 4460 KiB
23 Rossz válasz 14ms 4660 KiB
24 Rossz válasz 14ms 4508 KiB
subtask6 0/60
25 Rossz válasz 13ms 4452 KiB
26 Rossz válasz 14ms 4712 KiB
27 Rossz válasz 14ms 4568 KiB
28 Rossz válasz 13ms 4572 KiB
29 Rossz válasz 13ms 4572 KiB
30 Rossz válasz 13ms 4612 KiB
31 Rossz válasz 14ms 4616 KiB
32 Rossz válasz 14ms 4572 KiB
33 Rossz válasz 14ms 4768 KiB
34 Rossz válasz 14ms 4620 KiB
35 Rossz válasz 14ms 4876 KiB
36 Rossz válasz 14ms 4780 KiB
37 Rossz válasz 13ms 4784 KiB
38 Rossz válasz 14ms 4784 KiB
39 Rossz válasz 14ms 4784 KiB