oj.uz

Submission #777116

# Submission time Handle Problem Language Result Execution time Memory
777116 2023-07-08T16:59:38 Z PanosPask Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 891 ms 524288 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 (x->l == null) {
			x->l = new Node(0, -mid + 1, null, null);
		}
		if (x->r == null) {
			x->r = new Node(0, -rx + 1, null, null);
		}

		if (i < mid)
			modify(i, v, x->l, lx, mid);
		else
			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;
	}
	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(maxCoinSize);

	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 308 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 1 ms 312 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 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 1 ms 312 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 4 ms 3520 KB Output is correct
8 Correct 36 ms 26664 KB Output is correct
9 Correct 29 ms 26848 KB Output is correct
10 Correct 26 ms 25860 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 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 1 ms 312 KB Output is correct
6 Correct 247 ms 53404 KB Output is correct
7 Correct 229 ms 52892 KB Output is correct
8 Correct 272 ms 53440 KB Output is correct
9 Correct 445 ms 66424 KB Output is correct
10 Correct 439 ms 70792 KB Output is correct
11 Correct 138 ms 36956 KB Output is correct
12 Correct 142 ms 37072 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 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 1 ms 312 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 4 ms 3520 KB Output is correct
8 Correct 36 ms 26664 KB Output is correct
9 Correct 29 ms 26848 KB Output is correct
10 Correct 26 ms 25860 KB Output is correct
11 Correct 247 ms 53404 KB Output is correct
12 Correct 229 ms 52892 KB Output is correct
13 Correct 272 ms 53440 KB Output is correct
14 Correct 445 ms 66424 KB Output is correct
15 Correct 439 ms 70792 KB Output is correct
16 Correct 138 ms 36956 KB Output is correct
17 Correct 142 ms 37072 KB Output is correct
18 Correct 804 ms 425288 KB Output is correct
19 Correct 791 ms 442164 KB Output is correct
20 Runtime error 891 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -