Submission #457599

#	Time	Username	Problem	Language	Result	Execution time	Memory
457599		pavement	Candies (JOI18_candies)	C++17	100 / 100	403 ms	38072 KiB

candies

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, tot, A[200005], P[200005][2];
set<iii> s1, r1;

struct node {
	node *left, *right;
	int S, E;
	bool ip;
	ii val;
	node(int _s, int _e) : S(_s), E(_e), ip(0) {
		if (S == E) {
			val = mp(A[S], S);
			return;
		}
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
		val = max(left->val, right->val);
	}
	void prop() {
		if (S == E || !ip) return;
		left->val = right->val = mp(LLONG_MIN, LLONG_MIN);
		left->ip = right->ip = 1;
	}
	void set(int l, int r) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			val = mp(LLONG_MIN, LLONG_MIN);
			ip = 1;
			return;
		}
		prop();
		left->set(l, r);
		right->set(l, r);
		val = max(left->val, right->val);
	}
} *root;

void add(int l, int r) {
	vector<set<iii>::iterator> td;
	int newl = l, newr = r;
	auto it = r1.upper_bound(mt(r, LLONG_MAX, LLONG_MAX));
	if (it != r1.end() && g0(*it) == newr + 2) {
		newr = g1(*it);
		td.pb(it);
		if (s1.find(mt(g2(*it), g0(*it), g1(*it))) != s1.end()) s1.erase(mt(g2(*it), g0(*it), g1(*it)));
	}
	if (it != r1.begin()) {
		--it;
		if (g1(*it) == newl - 2) {
			newl = g0(*it);
			td.pb(it);
			if (s1.find(mt(g2(*it), g0(*it), g1(*it))) != s1.end()) s1.erase(mt(g2(*it), g0(*it), g1(*it)));
		}
		++it;
	}
	for (auto i : td) r1.erase(i);
	assert((newl & 1) == (newr & 1));
	if (newl == 1 || newr == N) {
		r1.emplace(newl, newr, -1ll);
	} else {
		int nv = (P[newr + 1][(newr + 1) & 1] - P[newl - 2][(newr + 1) & 1]) - (P[newr + 1][newr & 1] - P[newl - 2][newr & 1]);
		s1.emplace(nv, newl, newr);
		r1.emplace(newl, newr, nv);
	}
	root->set(max(1ll, newl - 1), min(N, newr + 1));
}

void tks1() {
	assert(!s1.empty());
	auto [v, l, r] = *s1.rbegin();
	assert(l != 1 && r != N);
	s1.erase(--s1.end());
	r1.erase(r1.find(mt(l, r, v)));
	tot += v;
	add(l - 1, r + 1);
}

void tks2() {
	auto v = root->val;
	tot += v.first;
	add(v.second, v.second);
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		P[i][0] = (i & 1 ? 0 : A[i]) + P[i - 1][0];
		P[i][1] = (i & 1 ? A[i] : 0) + P[i - 1][1];
	}
	root = new node(1, N);
	for (int i = 1; i <= (N + 1) / 2; i++) {
		if (s1.empty()) {
			tks2();
		} else {
			if (g0(*s1.rbegin()) > root->val.first) {
				tks1();
			} else {
				tks2();
			}
		}
		cout << tot << '\n';
	}
}

Compilation message (stderr)

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

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