#include "happiness.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") -> " << #x << " is " << (x) << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7;
const ll oo = 1e18;
ll C;
struct node { // maintain min{ a_i - s_{i - 1} }
ll s, mn, lz_add;
node *l, *r;
node() {
l = r = nullptr;
s = lz_add = 0;
mn = oo;
}
};
node* root = nullptr;
void pull(node* t) {
assert(t && t -> l && t -> r);
t -> mn = min(t -> l -> mn, t -> r -> mn);
}
void apply(node* &t, ll val) { // add val
if(!t) t = new node();
t -> mn += val;
t -> lz_add += val;
t -> s += val;
}
void push(node* t) {
assert(t);
apply(t -> l, t -> lz_add);
apply(t -> r, t -> lz_add);
t -> lz_add = 0;
}
ll qsum(node* t, ll pos, ll tl = 0, ll tr = C) {
if(!t) return 0;
if(tr - tl == 1) {
assert(pos == tl);
return t -> s;
}
push(t);
ll tm = (tl + tr) / 2;
if(pos < tm) return qsum(t -> l, pos, tl, tm);
else return qsum(t -> r, pos, tm, tr);
}
void set_mn(node* &t, ll pos, ll val, ll tl = 0, ll tr = C) {
if(!t) t = new node();
if(tr - tl == 1) {
assert(pos == tl);
t -> mn = val;
return;
}
push(t);
ll tm = (tl + tr) / 2;
if(pos < tm) set_mn(t -> l, pos, val, tl, tm);
else set_mn(t -> r, pos, val, tm, tr);
pull(t);
}
void add(node* &t, ll l, ll r, ll val, ll tl = 0, ll tr = C) {
if(!t) t = new node();
if(l <= tl && tr <= r) {
apply(t, val);
return;
}
push(t);
ll tm = (tl + tr) / 2;
if(l < tm) add(t -> l, l, r, val, tl, tm);
if(r > tm) add(t -> r, l, r, val, tm, tr);
pull(t);
}
map<ll, int> cnt;
void add_coins(ll val) {
assert(val < C);
ll cur = qsum(root, val) - val;
set_mn(root, val, cur);
if(val + 1 < C)
add(root, val + 1, C, val);
cnt[val]++;
}
void del_coins(ll val) {
assert(val < C);
assert(cnt[val]);
if(val + 1 < C)
add(root, val + 1, C, -val);
cnt[val]--;
if(cnt[val] == 0)
set_mn(root, val, oo);
}
bool happy() {
assert(root);
if(root -> mn < -1 || cnt[1] == 0) return false;
else return true;
}
void free_mem(node* t) {
if(!t) return;
free_mem(t -> l);
free_mem(t -> r);
delete t;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
cnt.clear();
free_mem(root);
root = nullptr;
C = maxCoinSize + 1;
for(int i = 0; i < coinsCount; i++) {
add_coins(coins[i]);
}
return happy();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
if(event == 1) { // add
for(int i = 0; i < coinsCount; i++)
add_coins(coins[i]);
} else { // del
for(int i = 0; i < coinsCount; i++)
del_coins(coins[i]);
}
return 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 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
