oj.uz

Submission #777127

# Submission time Handle Problem Language Result Execution time Memory
777127 2023-07-08T17:30:21 Z PanosPask Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 966 ms 379524 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 sum;
		ll min;

		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);
	}

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

			return;
		}

		ll mid = (lx + rx) / 2;

		if (i < mid) {
			if (x->l == null) {
				x->l = new Node(0, -mid + 1, null, null);
			}
			modify(i, v, x->l, lx, mid);

			ll m = x->r == null ? -rx + 1 : x->r->min;
			x->min = min(x->l->min, x->l->sum + m);
		}
		else {
			if (x->r == null) {
				x->r = new Node(0, -rx + 1, null, null);
			}
			modify(i, v, x->r, mid, rx);

			ll s = x->l->sum;
			ll m = x->l == null ? -mid + 1 : x->l->min;
			x->min = min(m, s + x->r->min);
		}

		x->sum += v * i;

		return;
	}
	void modify(ll i, ll v) {
		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) {
		pl v = calc(l, r, root, 0, size);
		// cerr << v.first << endl;
		return v.second;
	}
};

SegTree st;
ll M;
ll cursum = 0;

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

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

	sort(coins, coins + coinsCount);

	for (int i = 0; i < coinsCount; i++) {
		st.modify(coins[i], 1);
		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

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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 22 ms 13904 KB Output is correct
9 Correct 21 ms 14036 KB Output is correct
10 Correct 18 ms 13552 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 226 ms 34252 KB Output is correct
7 Correct 229 ms 33868 KB Output is correct
8 Correct 255 ms 34364 KB Output is correct
9 Correct 394 ms 44092 KB Output is correct
10 Correct 408 ms 48112 KB Output is correct
11 Correct 155 ms 33300 KB Output is correct
12 Correct 154 ms 33348 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 22 ms 13904 KB Output is correct
9 Correct 21 ms 14036 KB Output is correct
10 Correct 18 ms 13552 KB Output is correct
11 Correct 226 ms 34252 KB Output is correct
12 Correct 229 ms 33868 KB Output is correct
13 Correct 255 ms 34364 KB Output is correct
14 Correct 394 ms 44092 KB Output is correct
15 Correct 408 ms 48112 KB Output is correct
16 Correct 155 ms 33300 KB Output is correct
17 Correct 154 ms 33348 KB Output is correct
18 Correct 563 ms 220076 KB Output is correct
19 Correct 603 ms 228764 KB Output is correct
20 Correct 966 ms 379524 KB Output is correct
21 Correct 519 ms 198820 KB Output is correct
22 Correct 235 ms 39060 KB Output is correct
23 Correct 224 ms 39628 KB Output is correct
24 Correct 532 ms 216268 KB Output is correct