| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 410384 | fvogel499 | Happiness (Balkan15_HAPPINESS) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
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 ll long long
const ll pow2 = 1LL<<40LL;
const ll inf = 2e17;
struct Node {
Node(ll llb, ll lrb) {
lb = llb;
rb = lrb;
mxv = 0;
lzy = 0;
ln = nullptr;
rn = nullptr;
}
void extend() {
if (ln == 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(ll l, ll r, ll& 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);
}
}
ll lb, rb, mxv, lzy;
Node* ln, *rn;
};
Node* root;
map<ll, ll> s;
bool check() {
if (s.size() == 0) return true;
else {
ll 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(ll n, ll* b) {
for (ll 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(ll n, ll* b) {
for (ll 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(int n, ll maxVal, ll* b) {
root = new Node(0, pow2-1);
root->rangeUpdate(0, pow2-1, pow2-1-inf);
add(n, b);
return check();
}
bool is_happy(int event, int n, ll* b) {
if (event == 1) add(n, b);
else rem(n, b);
return check();
}
// signed main() {
// cin.tie(0);
// // ios_base::sync_with_stdio(0);
// ll n, maxVal;
// cin >> n >> maxVal;
// ll* b = new ll [n];
// for (ll i = 0; i < n; i++) cin >> b[i];
// cout << init(n, maxVal, b) << endl;
// ll nbReq;
// cin >> nbReq;
// for (ll _ = 0; _ < nbReq; _++) {
// ll event, ln;
// cin >> event >> ln;
// ll* lb = new ll [ln];
// for (ll i = 0; i < ln; i++) cin >> lb[i];
// cout << is_happy(event, ln, lb) << endl;
// }
// ll d = 0;
// d++;
// }