oj.uz

Submission #301514

# Submission time Handle Problem Language Result Execution time Memory
301514 2020-09-18T03:37:14 Z Falcon Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1203 ms 31228 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 14 ms 1280 KB Output is correct
9 Correct 14 ms 1280 KB Output is correct
10 Correct 13 ms 1280 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 450 ms 17040 KB Output is correct
7 Correct 428 ms 16888 KB Output is correct
8 Correct 437 ms 17116 KB Output is correct
9 Correct 766 ms 25336 KB Output is correct
10 Correct 1203 ms 28664 KB Output is correct
11 Correct 341 ms 26104 KB Output is correct
12 Correct 341 ms 26360 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 14 ms 1280 KB Output is correct
9 Correct 14 ms 1280 KB Output is correct
10 Correct 13 ms 1280 KB Output is correct
11 Correct 450 ms 17040 KB Output is correct
12 Correct 428 ms 16888 KB Output is correct
13 Correct 437 ms 17116 KB Output is correct
14 Correct 766 ms 25336 KB Output is correct
15 Correct 1203 ms 28664 KB Output is correct
16 Correct 341 ms 26104 KB Output is correct
17 Correct 341 ms 26360 KB Output is correct
18 Correct 584 ms 19448 KB Output is correct
19 Correct 608 ms 19896 KB Output is correct
20 Correct 1105 ms 31228 KB Output is correct
21 Correct 583 ms 19448 KB Output is correct
22 Correct 322 ms 28280 KB Output is correct
23 Correct 355 ms 28664 KB Output is correct
24 Correct 505 ms 19304 KB Output is correct