#include <bits/stdc++.h>
#define fi first
#define se second
#define fin(s) freopen( s, "r", stdin );
#define fout(s) freopen( s, "w", stdout );
const long long N = 200200;
const long long Q = 200200;
const long long mod = 998244353;
const long long MAGIC = sqrt(N);
using namespace std;
int n;
long long a[N];
set < int > s;
set < pair < long long, int > > f;
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
s.insert(i);
f.insert({a[i], i});
}
long long ans = 0;
for(int i = 1; i <= (n + 1) / 2; i++){
int x = (--f.end())->se;
f.erase(--f.end());
s.erase(x);
ans += a[x];
a[x] = - a[x];
auto p = s.lower_bound(x);
if(p != s.end()){
a[x] += a[*p];
f.erase({a[*p], *p});
s.erase(p);
}
p = s.lower_bound(x);
if(p != s.begin()){
p--;
a[x] += a[*p];
f.erase({a[*p], *p});
s.erase(p);
}
s.insert(x);
f.insert({a[x], x});
cout << ans << "\n";
}
}
bool mtest = false; int main()
{
//fin("input.txt");
//fout("output.txt");
//fin("island.in");
//fout("island.out");
ios_base::sync_with_stdio(0);
int TE = 1;
if(mtest)
cin >> TE;
while(TE--)
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
