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 |