//#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 = 0; i <= n + 1; 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 |
Correct |
9 ms |
896 KB |
Output is correct |
2 |
Correct |
9 ms |
896 KB |
Output is correct |
3 |
Correct |
8 ms |
896 KB |
Output is correct |
4 |
Correct |
9 ms |
896 KB |
Output is correct |
5 |
Correct |
9 ms |
896 KB |
Output is correct |
6 |
Correct |
8 ms |
1024 KB |
Output is correct |
7 |
Correct |
9 ms |
896 KB |
Output is correct |
8 |
Correct |
9 ms |
896 KB |
Output is correct |
9 |
Correct |
8 ms |
896 KB |
Output is correct |
10 |
Correct |
8 ms |
896 KB |
Output is correct |
11 |
Correct |
9 ms |
896 KB |
Output is correct |
12 |
Correct |
10 ms |
896 KB |
Output is correct |
13 |
Correct |
9 ms |
896 KB |
Output is correct |
14 |
Correct |
10 ms |
896 KB |
Output is correct |
15 |
Correct |
9 ms |
896 KB |
Output is correct |
16 |
Correct |
8 ms |
896 KB |
Output is correct |
17 |
Correct |
9 ms |
896 KB |
Output is correct |
18 |
Correct |
8 ms |
896 KB |
Output is correct |
19 |
Correct |
8 ms |
896 KB |
Output is correct |
20 |
Correct |
8 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
896 KB |
Output is correct |
2 |
Correct |
9 ms |
896 KB |
Output is correct |
3 |
Correct |
8 ms |
896 KB |
Output is correct |
4 |
Correct |
9 ms |
896 KB |
Output is correct |
5 |
Correct |
9 ms |
896 KB |
Output is correct |
6 |
Correct |
8 ms |
1024 KB |
Output is correct |
7 |
Correct |
9 ms |
896 KB |
Output is correct |
8 |
Correct |
9 ms |
896 KB |
Output is correct |
9 |
Correct |
8 ms |
896 KB |
Output is correct |
10 |
Correct |
8 ms |
896 KB |
Output is correct |
11 |
Correct |
9 ms |
896 KB |
Output is correct |
12 |
Correct |
10 ms |
896 KB |
Output is correct |
13 |
Correct |
9 ms |
896 KB |
Output is correct |
14 |
Correct |
10 ms |
896 KB |
Output is correct |
15 |
Correct |
9 ms |
896 KB |
Output is correct |
16 |
Correct |
8 ms |
896 KB |
Output is correct |
17 |
Correct |
9 ms |
896 KB |
Output is correct |
18 |
Correct |
8 ms |
896 KB |
Output is correct |
19 |
Correct |
8 ms |
896 KB |
Output is correct |
20 |
Correct |
8 ms |
896 KB |
Output is correct |
21 |
Correct |
1184 ms |
52344 KB |
Output is correct |
22 |
Correct |
1135 ms |
52584 KB |
Output is correct |
23 |
Correct |
1158 ms |
52488 KB |
Output is correct |
24 |
Correct |
534 ms |
52216 KB |
Output is correct |
25 |
Correct |
543 ms |
52152 KB |
Output is correct |
26 |
Correct |
535 ms |
52088 KB |
Output is correct |
27 |
Correct |
553 ms |
52416 KB |
Output is correct |
28 |
Correct |
576 ms |
52344 KB |
Output is correct |
29 |
Correct |
558 ms |
52344 KB |
Output is correct |
30 |
Correct |
580 ms |
52344 KB |
Output is correct |
31 |
Correct |
588 ms |
52448 KB |
Output is correct |
32 |
Correct |
591 ms |
52444 KB |
Output is correct |
33 |
Correct |
805 ms |
52088 KB |
Output is correct |
34 |
Correct |
763 ms |
52344 KB |
Output is correct |
35 |
Correct |
796 ms |
52216 KB |
Output is correct |
36 |
Correct |
1104 ms |
52344 KB |
Output is correct |
37 |
Correct |
1160 ms |
52344 KB |
Output is correct |
38 |
Correct |
1132 ms |
52260 KB |
Output is correct |
39 |
Correct |
529 ms |
52088 KB |
Output is correct |
40 |
Correct |
515 ms |
52216 KB |
Output is correct |
41 |
Correct |
530 ms |
52088 KB |
Output is correct |
42 |
Correct |
556 ms |
52344 KB |
Output is correct |
43 |
Correct |
559 ms |
52396 KB |
Output is correct |
44 |
Correct |
550 ms |
52472 KB |
Output is correct |
45 |
Correct |
590 ms |
52472 KB |
Output is correct |
46 |
Correct |
582 ms |
52432 KB |
Output is correct |
47 |
Correct |
610 ms |
52356 KB |
Output is correct |
48 |
Correct |
794 ms |
52216 KB |
Output is correct |
49 |
Correct |
804 ms |
52216 KB |
Output is correct |
50 |
Correct |
786 ms |
52316 KB |
Output is correct |