oj.uz

Submission #775366

# Submission time Handle Problem Language Result Execution time Memory
775366 2023-07-06T10:19:40 Z VMaksimoski008 Happiness (Balkan15_HAPPINESS) C++14
10 / 100
 274 ms 34296 KB 
#include "happiness.h"
using ll = long long;

struct Node {
	ll sum = 0;
	Node *lc, *rc;
	ll l, r;

	Node(ll l, ll r) : l(l), r(r), lc(nullptr), rc(nullptr) {}

	void update(int pos, int val) {
		sum += val;
		if(l == r) return;

		auto tm = (l + r) / 2;
		if(pos <= tm) {
			if(lc == nullptr) lc = new Node(l, tm);
			lc->update(pos, val);
		} else {
			if(rc == nullptr) rc = new Node(tm+1, r);
			rc->update(pos, val);
		}
	}

	ll query(int tl, int tr) {
		if(tl > r || l > tr) return 0;
		if(r <= tr && l >= tl) return this->sum;

		ll res = 0;
		if(lc) res += lc->query(tl, tr);
		if(rc) res += rc->query(tl, tr);
		return res;
	}
};

Node *root;

bool check() {
	ll curr = 1;
	ll sum = root->sum;

	while(sum > curr) {
		ll res = root->query(1, curr);
		if(res < curr) return 0;
		curr = res + 1;
	}

	return 1;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	root = new Node(1, maxCoinSize);
	for(int i=0; i<coinsCount; i++)
		root->update(coins[i], coins[i]);
	return check();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	for(int i=0; i<coinsCount; i++) {
		if(event == -1) root->update(coins[i], 0 - coins[i]);
		else root->update(coins[i], coins[i]);
	}
	return check();
}

Compilation message

happiness.cpp: In constructor 'Node::Node(ll, ll)':
happiness.cpp:7:8: warning: 'Node::r' will be initialized after [-Wreorder]
    7 |  ll l, r;
      |        ^
happiness.cpp:6:8: warning:   'Node* Node::lc' [-Wreorder]
    6 |  Node *lc, *rc;
      |        ^~
happiness.cpp:9:2: warning:   when initialized here [-Wreorder]
    9 |  Node(ll l, ll r) : l(l), r(r), lc(nullptr), rc(nullptr) {}
      |  ^~~~
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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 852 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 274 ms 34296 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 852 KB Output isn't correct
7 Halted 0 ms 0 KB -