Submission #247492

#	Time	Username	Problem	Language	Result	Execution time	Memory
247492		RealSuperman1	Candies (JOI18_candies)	C++17	100 / 100	1184 ms	52584 KiB

candies

//#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 (stderr)

candies.cpp:69:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92