Submission #368185

#	Time	Username	Problem	Language	Result	Execution time	Memory
368185		cheissmart	Happiness (Balkan15_HAPPINESS)	C++14	30 / 100	2085 ms	78884 KiB

happiness

    #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;
      |            ^~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40