//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragme GCC target("avx2");
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
//#define int long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fsdalfjlas x1
#define djfdslfka y1
using namespace std;
using namespace __gnu_pbds;
/*
st.insert(k);
st.find_by_order(k); iterator on k-th from 0
st.order_of_key(k); strictly less than k
*/
typedef
tree<
ll,
null_type,
less_equal<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
const ll mod = 1e9 + 7;
inline int modulo(int x) {x %= mod; return (x + mod) % mod; }
inline int mult(int x, int y) { ll x1 = modulo(x), y1 = modulo(y); return (x1 * y1) % (mod * 1ll); }
//inline void add(int &x, int y) { x = modulo(x + y); }
inline void Max(int &x, int y) { x = max(x, y); }
inline void Min(int &x, int y) { x = min(x, y); }
const int blocksz = 300;
const int inf = 1e9;
const ll INF = 1e16 + 2;
const int N = 2e5 + 123;
const int M = 2e5 + 10;
const int LIM = 1000000000;
ll n, a[N], ans = 0;
set <pair<ll, pll>> s;
set <ll> R;
map <ll, ll> L;
map <pll, ll> val;
main() {
ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
cin.tie(NULL); cout.tie(NULL);
// freopen("input.txt", "r", stdin);
// freopen("input.in", "r", stdin);
// freopen("input.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
a[0] = a[n + 1] = -INF;
for (int i = 1; i <= n; i++) {
R.insert(i);
L[i] = i;
s.insert({-a[i], {i, i}});
val[{i, i}] = a[i];
}
for (int i = 1; i <= (n + 1) / 2; i++) {
pair<ll, pll> tmp = *s.begin();
tmp.fi = -tmp.fi;
ans += tmp.fi;
ll l1, r1, l2, r2, l, r, v, v1, v2;
l = tmp.se.fi; r = tmp.se.se;
r1 = l - 1; l1 = L[r1];
r2 = *R.lower_bound(r + 1); l2 = L[r2];
v = val[{l, r}]; v1 = val[{l1, r1}]; v2 = val[{l2, r2}];
val.erase({l, r}); val.erase({l1, r1}); val.erase({l2, r2});
L.erase(r); L.erase(r1); L.erase(r2);
R.erase(r); R.erase(r1); R.erase(r2);
s.erase({-v, {l, r}}); s.erase({-v1, {l1, r1}}); s.erase({-v2, {l2, r2}});
s.insert({-(v1 + v2 - v), {l1, r2}});
R.insert(r2);
L[r2] = l1;
val[{l1, r2}] = v1 + v2 - v;
cout << ans << "\n";
}
}
Compilation message
candies.cpp:69:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
