Submission #456188

#	Time	Username	Problem	Language	Result	Execution time	Memory
456188		pavement	Candies (JOI18_candies)	C++17	0 / 100	2 ms	452 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 pf push_front
#define ppb pop_back
#define ppf pop_front
#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)
typedef double db;
typedef long long ll;
typedef long double ld;
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> rng, rng2, s, s2;

auto rmq(int l, int r) {
	auto ret = mp(LLONG_MIN, LLONG_MIN);
	for (int i = l; i <= r; i++)
		ret = max(ret, mp(A[i], i));
	return ret;
}

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

void tks() {
	//cout << "TKS\n";
	auto [v, l, r] = *s.rbegin();
	assert(l != 1 && r != N);
	rng.erase(rng.find(mt(l, r, v)));
	s.erase(--s.end());
	tot += v;
	sadd(l - 1, r + 1);
}

void tks2() {
	//cout << "TKS2\n";
	auto [v, l, r] = *s2.rbegin();
	tot += v;
	auto tmp = rmq(l, r);
	rng2.erase(mt(l, r, v));
	s2.erase(--s2.end());
	if (l <= tmp.second - 2) {
		s2.emplace(rmq(l, tmp.second - 2).first, l, tmp.second - 2);
		rng2.emplace(l, tmp.second - 2, rmq(l, tmp.second - 2).first);
	}
	if (tmp.second + 2 <= r) {
		s2.emplace(rmq(tmp.second + 2, r).first, tmp.second + 2, r);
		rng2.emplace(tmp.second + 2, r, rmq(tmp.second + 2, r).first);
	}
	sadd(tmp.second, tmp.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];
	}
	rng2.emplace(1, N, rmq(1, N).first);
	s2.emplace(rmq(1, N).first, 1, N);
	for (int i = 1; i <= (N + 1) / 2; i++) {
		while (!s.empty() && (g1(*s.rbegin()) == 1 || g2(*s.rbegin()) == N)) s.erase(--s.end());
		if (!s.empty() && !s2.empty()) {
			if (g0(*s.rbegin()) > g0(*s2.rbegin())) tks();
			else tks2();
		} else if (!s.empty()) {
			tks();
		} else {
			assert(!s2.empty());
			tks2();
		}
		//for (auto i : rng) cout << g0(i) << ' ' << g1(i) << ' ' << g2(i) << '\n';
		//cout << "--\n";
		//for (auto i : rng2) cout << g0(i) << ' ' << g1(i) << ' ' << g2(i) << '\n';
		//cout << "--\n";
		cout << tot << '\n';
	}
}

Compilation message (stderr)

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

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