oj.uz

Submission #368194

# Submission time Handle Problem Language Result Execution time Memory
368194 2021-02-19T18:36:05 Z cheissmart Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1982 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 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 -> mn, t -> r -> mn);
}

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;
	}
	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:70:3: note: in expansion of macro 'assert'
   70 |   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:82:3: note: in expansion of macro 'assert'
   82 |   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:109:2: note: in expansion of macro 'assert'
  109 |  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:118:2: note: in expansion of macro 'assert'
  118 |  assert(val < C);
      |  ^~~~~~
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(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:128:2: note: in expansion of macro 'assert'
  128 |  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 492 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 492 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 7 ms 3308 KB Output is correct
7 Correct 7 ms 3692 KB Output is correct
8 Correct 77 ms 27176 KB Output is correct
9 Correct 74 ms 27372 KB Output is correct
10 Correct 72 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 492 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 880 ms 61272 KB Output is correct
7 Correct 785 ms 60724 KB Output is correct
8 Correct 929 ms 61616 KB Output is correct
9 Correct 1369 ms 79544 KB Output is correct
10 Correct 1404 ms 83468 KB Output is correct
11 Correct 606 ms 51056 KB Output is correct
12 Correct 611 ms 51324 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 492 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 7 ms 3308 KB Output is correct
7 Correct 7 ms 3692 KB Output is correct
8 Correct 77 ms 27176 KB Output is correct
9 Correct 74 ms 27372 KB Output is correct
10 Correct 72 ms 26476 KB Output is correct
11 Correct 880 ms 61272 KB Output is correct
12 Correct 785 ms 60724 KB Output is correct
13 Correct 929 ms 61616 KB Output is correct
14 Correct 1369 ms 79544 KB Output is correct
15 Correct 1404 ms 83468 KB Output is correct
16 Correct 606 ms 51056 KB Output is correct
17 Correct 611 ms 51324 KB Output is correct
18 Correct 1843 ms 431636 KB Output is correct
19 Correct 1904 ms 451648 KB Output is correct
20 Runtime error 1982 ms 524292 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -