oj.uz

Submission #368187

# Submission time Handle Problem Language Result Execution time Memory
368187 2021-02-19T18:10:59 Z cheissmart Happiness (Balkan15_HAPPINESS) C++14
30 / 100
 2000 ms 90280 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);
}

void free_mem(node* t) {
	if(!t) return;
	free_mem(t -> l);
	free_mem(t -> r);
	delete t;
}

void init_ds() {
	// free_mem(root);
	root = nullptr;
}

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;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	cnt.clear();
	init_ds();

	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 1 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 1 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 8 ms 3308 KB Output is correct
7 Correct 9 ms 3564 KB Output is correct
8 Correct 88 ms 27244 KB Output is correct
9 Correct 109 ms 27500 KB Output is correct
10 Correct 78 ms 26476 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1313 ms 61908 KB Output is correct
7 Correct 1224 ms 61164 KB Output is correct
8 Correct 1263 ms 61932 KB Output is correct
9 Correct 1978 ms 78924 KB Output is correct
10 Execution timed out 2036 ms 90280 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 8 ms 3308 KB Output is correct
7 Correct 9 ms 3564 KB Output is correct
8 Correct 88 ms 27244 KB Output is correct
9 Correct 109 ms 27500 KB Output is correct
10 Correct 78 ms 26476 KB Output is correct
11 Correct 1313 ms 61908 KB Output is correct
12 Correct 1224 ms 61164 KB Output is correct
13 Correct 1263 ms 61932 KB Output is correct
14 Correct 1978 ms 78924 KB Output is correct
15 Execution timed out 2036 ms 90280 KB Time limit exceeded
16 Halted 0 ms 0 KB -