oj.uz

Submission #777100

# Submission time Handle Problem Language Result Execution time Memory
777100 2023-07-08T16:34:49 Z PanosPask Happiness (Balkan15_HAPPINESS) C++14
0 / 100
 1 ms 212 KB 
#include "happiness.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll, ll> pl;

struct SegTree {
	const ll NO_OP = 0;
	struct Node {
		// v is min(a[i] - i) for all i in node
		ll min;
		ll sum;

		Node *l, *r;

		Node(ll a, ll b, Node* c, Node* d) : sum(a), min(b), l(c), r(d) {};
	};
	Node* null;
	const pl NEUTRAL = {0, 0};

	ll size;
	Node* root;
	void init(ll n) {
		size = 1;
		while (size < n)
			size *= 2;

		null = new Node(0, 0, nullptr, nullptr);
		null->l = null->r = null;
		root = new Node(0, -size + 1, null, null);
	}

	Node* modify(ll i, ll v, Node* x, ll lx, ll rx) {
		if (x == null) {
			x = new Node(0, -rx + 1, null, null);
		}
		if (lx == rx - 1) {
			x->sum += v * i;
			x->min += v * i;

			return x;
		}

		ll mid = (lx + rx) / 2;
		if (i < mid)
			x->l = modify(i, v, x->l, lx, mid);
		else
			x->r = modify(i, v, x->r, mid, rx);

		x->sum = x->l->sum + x->r->sum;
		x->min = min(x->l->min, x->l->sum + x->r->min);

		return x;
	}
	void modify(ll i, ll v) {
		root = modify(i, v, root, 0, size);
	}

	pl calc(ll l, ll r, Node* x, ll lx, ll rx) {
		if (l >= rx || lx >= r) {
			return NEUTRAL;
		}
		if (x == null) {
			return {0, -min(r, rx)};
		}
		else if (l <= lx && rx <= r) {
			return {x->sum, x->min};
		}

		ll mid = (lx + rx) / 2;
		pl p1 = calc(l, r, x->l, lx, mid);
		pl p2 = calc(l, r, x->r, mid, rx);

		return {p1.first + p2.first, min(p1.second, p1.first + p2.second)};
	}
	ll calc(ll l, ll r) {
		return calc(l, r, root, 0, size).second;
	}
};

SegTree st;
ll M;
ll cursum = 0;

int checkgood(void)
{
	ll v = st.calc(0, min(M, cursum));
	// fprintf(stderr, "%lld\n", v);
	return v >= 0;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	M = maxCoinSize + 1;
	st.init(maxCoinSize);

	sort(coins, coins + coinsCount);

	for (int i = 0; i < coinsCount; i++) {
		st.modify(coins[i], 1);
		// fprintf(stderr, "Proccessing %lld, ans is %d\n", coins[i], checkgood());
		cursum += coins[i];
	}

	return checkgood();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	for (int i = 0; i < coinsCount; i++) {
		st.modify(coins[i], event);
		cursum += coins[i] * event;
	}

	return checkgood();
}

Compilation message

happiness.cpp: In constructor 'SegTree::Node::Node(ll, ll, SegTree::Node*, SegTree::Node*)':
happiness.cpp:15:6: warning: 'SegTree::Node::sum' will be initialized after [-Wreorder]
   15 |   ll sum;
      |      ^~~
happiness.cpp:14:6: warning:   'll SegTree::Node::min' [-Wreorder]
   14 |   ll min;
      |      ^~~
happiness.cpp:19:3: warning:   when initialized here [-Wreorder]
   19 |   Node(ll a, ll b, Node* c, Node* d) : sum(a), min(b), l(c), r(d) {};
      |   ^~~~
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 40.0

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