oj.uz

Submission #368191

# Submission time Handle Problem Language Result Execution time Memory
368191 2021-02-19T18:27:54 Z cheissmart Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1942 ms 524292 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 s, mn, lz_add;
	node *l, *r;
	bool clear;
	node() {
		l = r = nullptr;
		s = 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 -> 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 clear(node*& t) {
	if(!t) return;
	t = new node();
	t -> clear = true;
}

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

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:58:2: note: in expansion of macro 'assert'
   58 |  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:71:3: note: in expansion of macro 'assert'
   71 |   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:83:3: note: in expansion of macro 'assert'
   83 |   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:110:2: note: in expansion of macro 'assert'
  110 |  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:119:2: note: in expansion of macro 'assert'
  119 |  assert(val < C);
      |  ^~~~~~
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(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:129:2: note: in expansion of macro 'assert'
  129 |  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 0 ms 364 KB Output is correct
2 Correct 0 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 0 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 4332 KB Output is correct
7 Correct 9 ms 4720 KB Output is correct
8 Correct 88 ms 35692 KB Output is correct
9 Correct 96 ms 36076 KB Output is correct
10 Correct 74 ms 34796 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 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 940 ms 74640 KB Output is correct
7 Correct 888 ms 73884 KB Output is correct
8 Correct 935 ms 74812 KB Output is correct
9 Correct 1471 ms 95220 KB Output is correct
10 Correct 1457 ms 102064 KB Output is correct
11 Correct 730 ms 59356 KB Output is correct
12 Correct 676 ms 59356 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 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 4332 KB Output is correct
7 Correct 9 ms 4720 KB Output is correct
8 Correct 88 ms 35692 KB Output is correct
9 Correct 96 ms 36076 KB Output is correct
10 Correct 74 ms 34796 KB Output is correct
11 Correct 940 ms 74640 KB Output is correct
12 Correct 888 ms 73884 KB Output is correct
13 Correct 935 ms 74812 KB Output is correct
14 Correct 1471 ms 95220 KB Output is correct
15 Correct 1457 ms 102064 KB Output is correct
16 Correct 730 ms 59356 KB Output is correct
17 Correct 676 ms 59356 KB Output is correct
18 Runtime error 1942 ms 524292 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -