Submission #1306065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306065		danirasilla	Candies (JOI18_candies)	C++20	0 / 100	1 ms	572 KiB

candies

#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <iterator>
#include <set>
#include <random>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <stack>
#include <numeric>
#include <deque>

using namespace std;
typedef long long ll;
typedef long double ld;
const ll md1 = 1'000'000'007;
const ll md2 = 998244353;
const ll mdd = 666013;

ll ask(int l, int r) {
	cout << "? " << l + 1 << " " << r << endl;
	ll v;
	cin >> v;
	return v;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
	//cin >> t;
	while (t--) {

		int n;
		cin >> n;
		vector<ll> a(n);
		for (int i = 0; i < n; i++)
			cin >> a[i];
		priority_queue<pair<ll, pair<int, pair<int, int>>>> q;
		vector<int> l(n), r(n);
		vector<ll> prof = a;
		vector<int> it(n);
		iota(it.begin(), it.end(), 0);
		iota(l.begin(), l.end(), 0);
		iota(r.begin(), r.end(), 1);
		for (int i = 0; i < n; i++) 
			q.push({ a[i], { i, {l[i], r[i]} } });

		ll ans = 0;
		
		for (int I = 0; I < (n + 1) / 2; I++) {
			while (true) {
				auto nw = q.top();
				q.pop();
				if (nw.second.second.first != l[nw.second.first] || nw.second.second.second != r[nw.second.first])
					continue;
				int i = nw.second.first;
				ans += nw.first;
				cout << ans << "\n";
				a[i] += prof[i];
				prof[i] *= -1;
				bool ok = true;
				if (l[i]) {
					int ww = it[l[i] - 1];
					l[i] = l[ww];
					r[ww] = -1;
					l[ww] = -1;
					it[l[i]] = i;
					a[i] += a[ww];
					prof[i] += prof[ww];
				}
				else
					ok = false;
				if (r[i] < n) {
					int ww = it[r[i]];
					r[i] = r[ww];
					l[ww] = -1;
					r[ww] = -1;
					it[r[i] - 1] = i;
					a[i] += a[ww];
					prof[i] += prof[ww];
				}
				else
					ok = false;
				if (ok)
					q.push({ prof[i], {i, {l[i], r[i]}} });
				break;
			}
		}

	}
	return 0;
}

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