/*
File created on 05/22/2021 at 14:27:37.
Link to problem: https://oj.uz/problem/view/Balkan15_HAPPINESS
*/
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <happiness.h>
using namespace std;
#define int ll
#define ll long long
const int pow2 = 1LL<<40LL;
const int inf = 2e17;
struct Node {
Node(int llb, int lrb) {
lb = llb;
rb = lrb;
mxv = 0;
lzy = 0;
ln = nullptr;
rn = nullptr;
}
void extend() {
if (ln == nullptr and rn == nullptr) {
ln = new Node(lb, (lb+rb)/2);
ln->mxv = mxv-(rb-lb+1)/2;
rn = new Node((lb+rb)/2+1, rb);
rn->mxv = mxv;
}
}
void propag() {
if (lb != rb) {
extend();
ln->lzy += lzy;
rn->lzy += lzy;
}
mxv += lzy;
lzy = 0;
}
void rangeUpdate(int l, int r, int v) {
if (lb > r or l > rb) propag();
else if (l <= lb and rb <= r) {
lzy += v;
propag();
}
else {
propag();
ln->rangeUpdate(l, r, v);
rn->rangeUpdate(l, r, v);
mxv = max(ln->mxv, rn->mxv);
}
}
int lb, rb, mxv, lzy;
Node* ln, *rn;
};
Node* root;
map<int, int> s;
bool check() {
if (s.size() == 0) return true;
else {
int mxv = (*prev(s.end())).first;
root->rangeUpdate(mxv+1, pow2-1, -inf);
bool ans = (root->mxv <= 1);
root->rangeUpdate(mxv+1, pow2-1, +inf);
return ans;
}
}
void add(int n, int* b) {
for (int i = 0; i < n; i++) {
root->rangeUpdate(b[i]+1, pow2-1, -b[i]);
if (s.find(b[i]) == s.end() or s[b[i]] == 0) {
s[b[i]] = 1;
root->rangeUpdate(b[i], b[i], +inf);
}
else s[b[i]]++;
}
}
void rem(int n, int* b) {
for (int i = 0; i < n; i++) {
root->rangeUpdate(b[i]+1, pow2-1, +b[i]);
s[b[i]]--;
if (s[b[i]] == 0) {
s.erase(b[i]);
root->rangeUpdate(b[i], b[i], -inf);
}
}
}
bool init(unsigned n, int maxVal, int* b) {
root = new Node(0, pow2-1);
root->rangeUpdate(0, pow2-1, pow2-1);
root->rangeUpdate(0, pow2-1, -inf);
add(n, b);
return check();
}
bool is_happy(unsigned event, unsigned n, int* b) {
if (event == 1) add(n, b);
else rem(n, b);
return check();
}
// signed main() {
// cin.tie(0);
// // ios_base::sync_with_stdio(0);
// int n, maxVal;
// cin >> n >> maxVal;
// int* b = new int [n];
// for (int i = 0; i < n; i++) cin >> b[i];
// cout << init(n, maxVal, b) << endl;
// int nbReq;
// cin >> nbReq;
// for (int _ = 0; _ < nbReq; _++) {
// int event, ln;
// cin >> event >> ln;
// int* lb = new int [ln];
// for (int i = 0; i < ln; i++) cin >> lb[i];
// cout << is_happy(event, ln, lb) << endl;
// }
// int d = 0;
// d++;
// }
Compilation message
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
16 | long long max_code;
| ^~~~~~~~
/usr/bin/ld: /tmp/ccYOZP72.o: in function `main':
grader.cpp:(.text.startup+0x96): undefined reference to `init(int, long long, long long*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x160): undefined reference to `is_happy(int, int, long long*)'
collect2: error: ld returned 1 exit status
