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