Submission #512820

#TimeUsernameProblemLanguageResultExecution timeMemory
512820EyedHappiness (Balkan15_HAPPINESS)C++14
60 / 100
1613 ms524292 KiB
#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, int> numHas; ll m; struct node { int lN; int rN; ll a; //max over range bool mark; ll lazy; //need to add each element in v2 node(int l = -1, int r = -1, ll b = 0) : lN(l), rN(r), a(b), mark(false), lazy(0) {}; }; vector<node> st; void makeLeft(int v) { if (st[v].lN == -1) st[v].lN = st.size(), st.push_back(node()); } void makeRight(int v) { if (st[v].rN == -1) st[v].rN = st.size(), st.push_back(node()); } void makeChild(int v) { makeLeft(v); makeRight(v); } void push(int 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(int 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); ll mid = (tl + tr) / 2; if (max(l,tl) <= min(r,mid)) makeLeft(v), upd(st[v].lN, tl, mid, x, max(l, tl), min(r, mid)); if (max(l,mid+1) <= min(r,tr)) makeRight(v), upd(st[v].rN, mid + 1, tr, x, max(l, mid + 1), min(r, tr)); st[v].a = max((st[v].lN != -1 ? st[st[v].lN].a : 0), (st[v].rN != -1 ? st[st[v].rN].a : 0)); } void update(ll x, int e) { if (numHas.find(x) != numHas.end()) numHas[x]+=e; else numHas[x] = e; upd(0, 0, m, -e * x, x + 1, m); if (e == 1 && numHas[x] == 1) { upd(0, 0, m, x, x, x); } if (e == -1 && numHas[x] == 0) { upd(0, 0, m, -x, x, x); } } bool qry() { return st[0].a <= 1; } void init() { st.push_back(node()); } bool init(int coinsCount, long long maxCoinSize, long long coins[]) { m = maxCoinSize; init(); for (ll i = 0; i < coinsCount; ++i) update(coins[i], 1); return qry(); } bool is_happy(int event, int 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; //}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...