| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 512811 | Eyed | Happiness (Balkan15_HAPPINESS) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9 + 7;
map<ll, ll> numHas;
struct node {
ll lN;
ll rN;
ll a; //max over range
bool mark;
ll lazy; //need to add each element in v2
node(ll l = -1, ll r = -1, ll b = 0) : lN(l), rN(r), a(b), mark(false), lazy(0) {};
};
vector<node> st;
void makeChild(ll v) {
if (st[v].lN == -1) {
st[v].lN = st.size();
st.push_back(node(-1, -1, 0));
}
if (st[v].rN == -1) {
st[v].rN = st.size();
st.push_back(node(-1, -1, 0));
}
}
void push(ll v) {
if (st[v].mark) {
st[v].mark = false;
makeChild(v);
st[st[v].lN].mark = true;
st[st[v].rN].mark = true;
st[st[v].lN].lazy += st[v].lazy;
st[st[v].rN].lazy += st[v].lazy;
st[st[v].lN].a += st[v].lazy;
st[st[v].rN].a += st[v].lazy;
st[v].lazy = 0;
}
}
void upd(ll v, ll tl, ll tr, ll x, ll l, ll r) {
//upd adds x from l to r
if (l > r) return;
if (l <= tl && r >= tr) {
st[v].a += x;
st[v].lazy += x;
st[v].mark = true;
return;
}
push(v);
makeChild(v);
ll mid = (tl + tr) / 2;
upd(st[v].lN, tl, mid, x, max(l, tl), min(r, mid));
upd(st[v].rN, mid + 1, tr, x, max(l, mid + 1), min(r, tr));
st[v].a = max(st[st[v].lN].a, st[st[v].rN].a);
}
void update(ll x, ll e) {
if (numHas.find(x) != numHas.end()) numHas[x]+=e;
else numHas[x] = e;
upd(0, 0, 1e12, -e * x, x + 1, 1e12);
if (e == 1 && numHas[x] == 1) {
upd(0, 0, 1e12, x, x, x);
}
if (e == -1 && numHas[x] == 0) {
upd(0, 0, 1e12, -x, x, x);
}
}
bool qry() { return st[0].a <= 1; }
void init() { st.push_back(node()); }
bool init(ll coinsCount, long long maxCoinSize, long long coins[]) {
init();
for (ll i = 0; i < coinsCount; ++i) update(coins[i], 1);
return qry();
}
bool is_happy(ll event, ll coinsCount, long long coins[]) {
for (ll i = 0; i < coinsCount; ++i) update(coins[i], event);
return qry();
}
//ll main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
//
// long long arr[5] = { 1,2,4,8,16 };
// cout << init(5, 100, arr) << endl;
// ll a1[2] = { 2,8 };
// cout << is_happy(-1, 2, a1) << endl;
// ll a2[3] = { 7,9,2 };
// cout << is_happy(1, 3, a2) << endl;
//
// return 0;
//}