// Test problem: https://oj.uz/problem/view/Balkan15_HAPPINESS
#include <algorithm>
#include "happiness.h"
using namespace std;
const int LOG = 10; // should be ~40
const int MAX_N = 200000;
const int SZ = 4 * MAX_N * LOG;
class DynamicSegmentTree {
private:
struct State {
long long range_sum, range_min;
bool ok;
};
State v[SZ];
pair<int, int> sons[SZ];
vector<int> available;
void clear(int idx) {
v[idx].range_sum = v[idx].range_min = 0;
sons[idx].first = sons[idx].second = -1;
v[idx].ok = true;
}
void init(int idx) {
if (sons[idx].first == -1) {
sons[idx].first = available.back(), available.pop_back();
}
if (sons[idx].second == -1) {
sons[idx].second = available.back(), available.pop_back();
}
}
State merge(const State &a, const State &b) {
State res;
res.range_sum = a.range_sum + b.range_sum;
if (min(a.range_min, b.range_min) > 0) {
res.range_min = min(a.range_min, b.range_min);
} else {
res.range_min = max(a.range_min, b.range_min);
}
res.ok = a.ok && (1 + a.range_sum >= b.range_min);
return res;
}
public:
void Init() {
for (int i = SZ - 1; i >= 1; i--) {
available.push_back(i);
clear(i);
}
available.pop_back();
}
void Update(int idx, long long l, long long r, long long pos, int sgn, int par = -1) {
if (sons[idx].first == -1 || sons[idx].second == -1) {
init(idx);
}
if (l == r) {
v[idx].range_sum += sgn * pos;
v[idx].range_min = ((v[idx].range_sum > 0) ? pos : 0);
v[idx].ok = true;
if (v[idx].range_sum == 0) {
if (par == -1) return;
if (sons[par].first == idx) { sons[par].first = -1; }
else { sons[par].second = -1; }
clear(idx);
available.push_back(idx);
}
return;
}
long long mid = (l + r) >> 1;
if (pos <= mid) Update(sons[idx].first, l, mid, pos, sgn, idx);
else Update(sons[idx].second, mid + 1, r, pos, sgn, idx);
if (sons[idx].first == -1) {
v[idx] = (sons[idx].second != -1 ? v[sons[idx].second] : State{0, 0,true});
} else {
v[idx] = merge(v[sons[idx].first], (sons[idx].second != -1 ? v[sons[idx].second] : State{0, 0,true}));
}
}
bool GetValid() {
return v[1].ok;
}
};
DynamicSegmentTree dst;
int nr_coins, fv_1;
long long max_coin_size;
bool get_is_happy() {
return (nr_coins == 0) || (fv_1 >= 1 && dst.GetValid());
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
dst.Init();
nr_coins = coinsCount;
max_coin_size = maxCoinSize;
for (int i = 0; i < coinsCount; i++) {
dst.Update(1, 1, max_coin_size, coins[i], 1);
if (coins[i] == 1) fv_1++;
}
return get_is_happy();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
nr_coins += event * coinsCount;
for (int i = 0; i < coinsCount; i++) {
dst.Update(1, 1, max_coin_size, coins[i], event);
if (coins[i] == 1) fv_1 += event;
}
return get_is_happy();
}
Compilation message
happiness.cpp:21:5: error: 'vector' does not name a type
21 | vector<int> available;
| ^~~~~~
happiness.cpp: In member function 'void DynamicSegmentTree::init(int)':
happiness.cpp:31:31: error: 'available' was not declared in this scope
31 | sons[idx].first = available.back(), available.pop_back();
| ^~~~~~~~~
happiness.cpp:34:32: error: 'available' was not declared in this scope
34 | sons[idx].second = available.back(), available.pop_back();
| ^~~~~~~~~
happiness.cpp: In member function 'void DynamicSegmentTree::Init()':
happiness.cpp:54:13: error: 'available' was not declared in this scope
54 | available.push_back(i);
| ^~~~~~~~~
happiness.cpp:57:9: error: 'available' was not declared in this scope
57 | available.pop_back();
| ^~~~~~~~~
happiness.cpp: In member function 'void DynamicSegmentTree::Update(int, long long int, long long int, long long int, int, int)':
happiness.cpp:75:17: error: 'available' was not declared in this scope
75 | available.push_back(idx);
| ^~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
16 | long long max_code;
| ^~~~~~~~
