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