Submission #301514

#	Time	Username	Problem	Language	Result	Execution time	Memory
301514		Falcon	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	1203 ms	31228 KiB

happiness

#pragma GCC optimize("O2")
#include "happiness.h"
#include <bits/stdc++.h>
#ifdef DEBUG
	#include "debug.hpp"
#endif

using namespace std;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
	#define debug(x...) { dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals); }
	#define light_debug(x) { dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0; }
#else
	#define debug(x...)
	#define light_debug(x) 
#endif

template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> uid(1, 1 << 29);

class Treap {
	struct node {
		ll v;
		int p;
		ll sum, dp;
		node *l, *r;

		node(ll k) : 
			v{k},
			p{uid(rng)},
			sum{k},
			dp{1 - k}, 
			l{nullptr}, 
			r{nullptr} {}
	};

	using pnode = node*;

	inline ll sum(pnode t) const { return t ? t->sum : 0; }

	inline ll dp(pnode t) const { return t ? t->dp : 0; }

	inline void pull(pnode t) { if(t) t->sum = sum(t->l) + t->v + sum(t->r), t->dp = min({dp(t->l), 1 + sum(t->l) - t->v, dp(t->r) + sum(t->l) + t->v}); }

	pnode root{nullptr};

	void merge(pnode& t, pnode l, pnode r) {
		if(!l || !r)
			t = l ? l : r;
		else if(l->p >= r->p) 
			merge(l->r, l->r, r), t = l;
		else
			merge(r->l, l, r->l), t = r;
		pull(t);
	}

	void split(pnode t, pnode& l, pnode& r, ll v) {
		if(!t)
			l = r = nullptr;
		else if(t->v <= v)
			split(t->r, t->r, r, v), l = t;
		else
			split(t->l, l, t->l, v), r = t;
		pull(t);
	}

	void print(pnode t) const {
		if(!t) return;
		print(t->l);
		cerr << t->v << ' ';
		print(t->r);
	}

public:

	void insert(ll v) {
		pnode t = new node(v);
		pnode l, r;
		split(root, l, r, v);
		//cerr << "\tl: "; print(l), cerr << "\n\tr: "; print(r); cerr << '\n';
		merge(l, l, t);
		merge(root, l, r);
	}

	void erase(ll v) {
		pnode l, m, r;
		split(root, l, r, v);
		split(l, l, m, v - 1);
		assert(m); merge(m, m->l, m->r);
		merge(root, l, m);
		merge(root, root, r);
	}

	void print() const { cerr << "treap: "; print(root); cerr << endl; }

	bool is_happy() const { return dp(root) >= 0; }

};

Treap treap;

bool init(int N, ll M, ll coins[]) {
	rep(i, N)
		treap.insert(coins[i]);
	//treap.print();
	return treap.is_happy();
}

bool is_happy(int event, int K, ll coins[]) {
	rep(i, K) 
		if(~event) treap.insert(coins[i]);
		else treap.erase(coins[i]);
	//treap.print();
	return treap.is_happy();
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40