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 |