Submission #368185

#TimeUsernameProblemLanguageResultExecution timeMemory
368185cheissmartHappiness (Balkan15_HAPPINESS)C++14
30 / 100
2085 ms78884 KiB
#include "happiness.h" #include <bits/stdc++.h> #define F first #define S second #define PB push_back #define EB emplace_back #define MP make_pair #define V vector #define ALL(v) (v).begin(), (v).end() #define debug(x) cerr << "LINE(" << __LINE__ << ") -> " << #x << " is " << (x) << endl using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef V<int> vi; const int INF = 1e9 + 7; const ll oo = 1e18; ll C; struct node { // maintain min{ a_i - s_{i - 1} } ll s, mn, lz_add; node *l, *r; node() { l = r = nullptr; s = lz_add = 0; mn = oo; } }; node* root = nullptr; void pull(node* t) { assert(t && t -> l && t -> r); t -> mn = min(t -> l -> mn, t -> r -> mn); } void apply(node* &t, ll val) { // add val if(!t) t = new node(); t -> mn += val; t -> lz_add += val; t -> s += val; } void push(node* t) { assert(t); apply(t -> l, t -> lz_add); apply(t -> r, t -> lz_add); t -> lz_add = 0; } ll qsum(node* t, ll pos, ll tl = 0, ll tr = C) { if(!t) return 0; if(tr - tl == 1) { assert(pos == tl); return t -> s; } push(t); ll tm = (tl + tr) / 2; if(pos < tm) return qsum(t -> l, pos, tl, tm); else return qsum(t -> r, pos, tm, tr); } void set_mn(node* &t, ll pos, ll val, ll tl = 0, ll tr = C) { if(!t) t = new node(); if(tr - tl == 1) { assert(pos == tl); t -> mn = val; return; } push(t); ll tm = (tl + tr) / 2; if(pos < tm) set_mn(t -> l, pos, val, tl, tm); else set_mn(t -> r, pos, val, tm, tr); pull(t); } void add(node* &t, ll l, ll r, ll val, ll tl = 0, ll tr = C) { if(!t) t = new node(); if(l <= tl && tr <= r) { apply(t, val); return; } push(t); ll tm = (tl + tr) / 2; if(l < tm) add(t -> l, l, r, val, tl, tm); if(r > tm) add(t -> r, l, r, val, tm, tr); pull(t); } map<ll, int> cnt; void add_coins(ll val) { assert(val < C); ll cur = qsum(root, val) - val; set_mn(root, val, cur); if(val + 1 < C) add(root, val + 1, C, val); cnt[val]++; } void del_coins(ll val) { assert(val < C); assert(cnt[val]); if(val + 1 < C) add(root, val + 1, C, -val); cnt[val]--; if(cnt[val] == 0) set_mn(root, val, oo); } bool happy() { assert(root); if(root -> mn < -1) return false; else return true; } void free_mem(node* t) { if(!t) return; free_mem(t -> l); free_mem(t -> r); delete t; } bool init(int coinsCount, long long maxCoinSize, long long coins[]) { cnt.clear(); free_mem(root); root = nullptr; C = maxCoinSize + 1; for(int i = 0; i < coinsCount; i++) { add_coins(coins[i]); } return happy(); } bool is_happy(int event, int coinsCount, long long coins[]) { if(event == 1) { // add for(int i = 0; i < coinsCount; i++) add_coins(coins[i]); } else { // del for(int i = 0; i < coinsCount; i++) del_coins(coins[i]); } return happy(); }

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...