#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// segment tree of a[i] - a[i-1] - a[i-2] - ... - a[1]
// maximum of this must be zero or less
// when adding a[i], update range [a[i], a[i]] with +a[i]
// and updating range [a[i]+1,inf] with -a[i]
// and do the opposite when removing
struct Node {
ll tag, mx;
Node *left, *right;
Node() : tag(0), mx(0), left(nullptr), right(nullptr) {}
void extend(ll xl, ll xr) {
if (xl != xr && !left) {
left = new Node();
right = new Node();
}
}
void apply(ll xl, ll xr) {
extend(xl, xr);
if (tag != 0) {
mx += tag;
if (left) left->tag += tag;
if (right) right->tag += tag;
tag = 0;
}
}
void update(ll l, ll r, ll xl, ll xr, ll delta) {
if (l > r) return;
if (l == xl && r == xr) {
tag += delta;
} else {
apply(xl, xr);
ll xm = (xl + xr) / 2;
left->update(l, min(r, xm), xl, xm, delta);
right->update(max(l, xm+1), r, xm+1, xr, delta);
left->apply(xl, xm); right->apply(xm+1, xr);
mx = max(left->mx, right->mx);
}
}
} tree;
const ll hi = 1'000'000'000'005LL;
void add(ll coin) {
tree.update(coin, coin, 1, hi, +coin);
tree.update(coin+1, hi, 1, hi, -coin);
}
void remove(ll coin) {
tree.update(coin, coin, 1, hi, -coin);
tree.update(coin+1, hi, 1, hi, +coin);
}
bool check() {
tree.apply(1, hi);
return tree.mx <= 1;
}
bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
for (int i=0; i<coinsCount; i++) add(coins[i]);
return check();
}
bool is_happy(int event, int coinsCount, ll coins[]) {
for (int i=0; i<coinsCount; i++)
if (event == 1) add(coins[i]);
else remove(coins[i]);
return check();
}
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 |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
