#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());
}
bool is_last (ll I) {
auto it = idx.lower_bound(pll(Find(I), -inf));
it++;
return (it == idx.end());
}
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;
tie(A, B) = *val.begin();
R -= A;
if(!is_first(B)) {
X += Erase(B-1);
par[B] = B-1;
}
else F = 1;
if(!is_last(B)) {
X += Erase(B+1);
par[B+1] = 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:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
candies.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&a[i]);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
