oj.uz

Submission #368196

# Submission time Handle Problem Language Result Execution time Memory
368196 2021-02-19T18:39:28 Z cheissmart Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1901 ms 524288 KB 
#include "happiness.h"
#include <unordered_map>
#include <cassert>
#pragma GCC optimize("Ofast", "no-stack-protector", "unroll-loops")
#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
#define assert(...) 5979

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;

const int INF = 1e9 + 7;
const ll oo = 1e18;

ll C;

struct node { // maintain min{ a_i - s_{i - 1} }
	ll mn, lz_add;
	node *l, *r;
	bool clear;
	node() {
		l = r = nullptr;
		lz_add = 0;
		mn = oo;
		clear = false;
	}
};

node* root = nullptr;

void pull(node* t) {
	assert(t && t -> l && t -> r);
	t -> mn = min(t -> l ? t -> l -> mn : oo, t -> r ? t -> r -> mn : oo);
}

void apply(node* &t, ll val) { // add val
	if(!t) t = new node();
	t -> mn += val;
	t -> lz_add += val;
}

void clear(node*& t) {
	if(!t) return;
	*t = node();
	t -> clear = true;
}

void push(node* t) {
	assert(t);
	if(t -> clear) {
		clear(t -> l), clear(t -> r);
		t -> clear = false;
	}
	if(t -> lz_add) {
		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 -> lz_add;
	}
	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);
}

unordered_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();
	clear(root);

	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

happiness.cpp:13: warning: "assert" redefined
   13 | #define assert(...) 5979
      | 
In file included from /usr/include/c++/9/cassert:44,
                 from happiness.cpp:3:
/usr/include/assert.h:92: note: this is the location of the previous definition
   92 | #  define assert(expr)       \
      | 
happiness.cpp: In function 'void pull(node*)':
happiness.cpp:13:21: warning: statement has no effect [-Wunused-value]
   13 | #define assert(...) 5979
      |                     ^~~~
happiness.cpp:40:2: note: in expansion of macro 'assert'
   40 |  assert(t && t -> l && t -> r);
      |  ^~~~~~
happiness.cpp: In function 'void push(node*)':
happiness.cpp:13:21: warning: statement has no effect [-Wunused-value]
   13 | #define assert(...) 5979
      |                     ^~~~
happiness.cpp:57:2: note: in expansion of macro 'assert'
   57 |  assert(t);
      |  ^~~~~~
happiness.cpp: In function 'll qsum(node*, ll, ll, ll)':
happiness.cpp:13:21: warning: statement has no effect [-Wunused-value]
   13 | #define assert(...) 5979
      |                     ^~~~
happiness.cpp:72:3: note: in expansion of macro 'assert'
   72 |   assert(pos == tl);
      |   ^~~~~~
happiness.cpp: In function 'void set_mn(node*&, ll, ll, ll, ll)':
happiness.cpp:13:21: warning: statement has no effect [-Wunused-value]
   13 | #define assert(...) 5979
      |                     ^~~~
happiness.cpp:84:3: note: in expansion of macro 'assert'
   84 |   assert(pos == tl);
      |   ^~~~~~
happiness.cpp: In function 'void add_coins(ll)':
happiness.cpp:13:21: warning: statement has no effect [-Wunused-value]
   13 | #define assert(...) 5979
      |                     ^~~~
happiness.cpp:111:2: note: in expansion of macro 'assert'
  111 |  assert(val < C);
      |  ^~~~~~
happiness.cpp: In function 'void del_coins(ll)':
happiness.cpp:13:21: warning: statement has no effect [-Wunused-value]
   13 | #define assert(...) 5979
      |                     ^~~~
happiness.cpp:120:2: note: in expansion of macro 'assert'
  120 |  assert(val < C);
      |  ^~~~~~
happiness.cpp:13:21: warning: statement has no effect [-Wunused-value]
   13 | #define assert(...) 5979
      |                     ^~~~
happiness.cpp:121:2: note: in expansion of macro 'assert'
  121 |  assert(cnt[val]);
      |  ^~~~~~
happiness.cpp: In function 'bool happy()':
happiness.cpp:13:21: warning: statement has no effect [-Wunused-value]
   13 | #define assert(...) 5979
      |                     ^~~~
happiness.cpp:130:2: note: in expansion of macro 'assert'
  130 |  assert(root);
      |  ^~~~~~
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 64 ms 27116 KB Output is correct
9 Correct 68 ms 27368 KB Output is correct
10 Correct 63 ms 26476 KB Output is correct

Subtask #3
30.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 781 ms 59188 KB Output is correct
7 Correct 792 ms 58420 KB Output is correct
8 Correct 796 ms 59188 KB Output is correct
9 Correct 1239 ms 76452 KB Output is correct
10 Correct 1332 ms 82112 KB Output is correct
11 Correct 535 ms 50268 KB Output is correct
12 Correct 485 ms 50396 KB Output is correct

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 64 ms 27116 KB Output is correct
9 Correct 68 ms 27368 KB Output is correct
10 Correct 63 ms 26476 KB Output is correct
11 Correct 781 ms 59188 KB Output is correct
12 Correct 792 ms 58420 KB Output is correct
13 Correct 796 ms 59188 KB Output is correct
14 Correct 1239 ms 76452 KB Output is correct
15 Correct 1332 ms 82112 KB Output is correct
16 Correct 535 ms 50268 KB Output is correct
17 Correct 485 ms 50396 KB Output is correct
18 Correct 1753 ms 431096 KB Output is correct
19 Correct 1800 ms 448912 KB Output is correct
20 Runtime error 1901 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -