#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 200005, inf = 1e18;
ll n, a[N], par[N];
bool dead[N];
set<pll> val, idx;
ll Find (ll X) {
if(par[X] == X) return X;
return par[X] = Find(par[X]);
}
ll Erase (ll X) {
ll A, B;
tie(A, B) = *idx.lower_bound(pll(Find(X), -inf));
idx.erase(pll(A, B));
val.erase(pll(B, A));
return B;
}
bool is_first (ll I) {
auto it = idx.lower_bound(pll(Find(I), -inf));
return (it == idx.begin());
}
ll next_el (ll I) {
auto it = idx.lower_bound(pll(Find(I), -inf));
it++;
if(it == idx.end()) return 0;
return (*it).first;
}
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++) {
scanf("%lld",&a[i]);
par[i] = i;
val.insert(pll(-a[i], i));
idx.insert(pll(i, -a[i]));
}
ll R = 0;
for(ll i=1;i<=(n+1)/2;i++) {
ll A, B, X = 0, F = 0, T;
tie(A, B) = *val.begin();
R -= A;
if(!is_first(B)) {
X += Erase(B-1);
par[B] = B-1;
}
else F = 1;
T = next_el(B);
if(T) {
X += Erase(T);
par[T] = B;
}
else F = 1;
val.erase(pll(A, B));
idx.erase(pll(B, A));
if(!F) {
A = X - A;
B = Find(B);
val.insert(pll(A, B));
idx.insert(pll(B, A));
}
printf("%lld\n",R);
}
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
candies.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&a[i]);
~~~~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
632 KB |
Output is correct |
| 2 |
Correct |
6 ms |
744 KB |
Output is correct |
| 3 |
Correct |
4 ms |
744 KB |
Output is correct |
| 4 |
Correct |
6 ms |
908 KB |
Output is correct |
| 5 |
Correct |
6 ms |
908 KB |
Output is correct |
| 6 |
Correct |
5 ms |
940 KB |
Output is correct |
| 7 |
Correct |
6 ms |
940 KB |
Output is correct |
| 8 |
Correct |
5 ms |
940 KB |
Output is correct |
| 9 |
Correct |
5 ms |
940 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1068 KB |
Output is correct |
| 11 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 12 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 14 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 15 |
Correct |
8 ms |
1068 KB |
Output is correct |
| 16 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 17 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 18 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 19 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 20 |
Correct |
6 ms |
1068 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
632 KB |
Output is correct |
| 2 |
Correct |
6 ms |
744 KB |
Output is correct |
| 3 |
Correct |
4 ms |
744 KB |
Output is correct |
| 4 |
Correct |
6 ms |
908 KB |
Output is correct |
| 5 |
Correct |
6 ms |
908 KB |
Output is correct |
| 6 |
Correct |
5 ms |
940 KB |
Output is correct |
| 7 |
Correct |
6 ms |
940 KB |
Output is correct |
| 8 |
Correct |
5 ms |
940 KB |
Output is correct |
| 9 |
Correct |
5 ms |
940 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1068 KB |
Output is correct |
| 11 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 12 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 14 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 15 |
Correct |
8 ms |
1068 KB |
Output is correct |
| 16 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 17 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 18 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 19 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 20 |
Correct |
6 ms |
1068 KB |
Output is correct |
| 21 |
Correct |
985 ms |
30364 KB |
Output is correct |
| 22 |
Correct |
1033 ms |
30364 KB |
Output is correct |
| 23 |
Correct |
1171 ms |
30384 KB |
Output is correct |
| 24 |
Correct |
475 ms |
30384 KB |
Output is correct |
| 25 |
Correct |
449 ms |
30384 KB |
Output is correct |
| 26 |
Correct |
417 ms |
30384 KB |
Output is correct |
| 27 |
Correct |
490 ms |
30384 KB |
Output is correct |
| 28 |
Correct |
472 ms |
30384 KB |
Output is correct |
| 29 |
Correct |
498 ms |
30384 KB |
Output is correct |
| 30 |
Correct |
496 ms |
30384 KB |
Output is correct |
| 31 |
Correct |
529 ms |
30396 KB |
Output is correct |
| 32 |
Correct |
535 ms |
30396 KB |
Output is correct |
| 33 |
Correct |
839 ms |
30396 KB |
Output is correct |
| 34 |
Correct |
813 ms |
30396 KB |
Output is correct |
| 35 |
Correct |
755 ms |
30396 KB |
Output is correct |
| 36 |
Correct |
1093 ms |
30524 KB |
Output is correct |
| 37 |
Correct |
960 ms |
30524 KB |
Output is correct |
| 38 |
Correct |
1056 ms |
30524 KB |
Output is correct |
| 39 |
Correct |
531 ms |
30524 KB |
Output is correct |
| 40 |
Correct |
483 ms |
30524 KB |
Output is correct |
| 41 |
Correct |
452 ms |
30524 KB |
Output is correct |
| 42 |
Correct |
478 ms |
30524 KB |
Output is correct |
| 43 |
Correct |
483 ms |
30524 KB |
Output is correct |
| 44 |
Correct |
424 ms |
30524 KB |
Output is correct |
| 45 |
Correct |
468 ms |
30524 KB |
Output is correct |
| 46 |
Correct |
462 ms |
30524 KB |
Output is correct |
| 47 |
Correct |
478 ms |
30524 KB |
Output is correct |
| 48 |
Correct |
891 ms |
30524 KB |
Output is correct |
| 49 |
Correct |
773 ms |
30524 KB |
Output is correct |
| 50 |
Correct |
752 ms |
30524 KB |
Output is correct |
