#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);
}
public:
void insert(ll v) {
pnode t = new node(v);
pnode l, r;
split(root, l, r, v);
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);
}
bool is_happy() const { return dp(root) >= 0; }
};
Treap treap;
bool init(int N, ll M, ll coins[]) {
rep(i, M)
treap.insert(coins[i]);
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]);
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;
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
640 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
640 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
640 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
640 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
