oj.uz

Submission #368185

# Submission time Handle Problem Language Result Execution time Memory
368185 2021-02-19T18:08:27 Z cheissmart Happiness (Balkan15_HAPPINESS) C++14
30 / 100
 2000 ms 78884 KB 
    #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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 9 ms 3308 KB Output is correct
7 Correct 9 ms 3564 KB Output is correct
8 Correct 90 ms 27244 KB Output is correct
9 Correct 88 ms 27500 KB Output is correct
10 Correct 82 ms 26732 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1325 ms 61860 KB Output is correct
7 Correct 1439 ms 61164 KB Output is correct
8 Correct 1395 ms 61888 KB Output is correct
9 Execution timed out 2085 ms 78884 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 9 ms 3308 KB Output is correct
7 Correct 9 ms 3564 KB Output is correct
8 Correct 90 ms 27244 KB Output is correct
9 Correct 88 ms 27500 KB Output is correct
10 Correct 82 ms 26732 KB Output is correct
11 Correct 1325 ms 61860 KB Output is correct
12 Correct 1439 ms 61164 KB Output is correct
13 Correct 1395 ms 61888 KB Output is correct
14 Execution timed out 2085 ms 78884 KB Time limit exceeded
15 Halted 0 ms 0 KB -