oj.uz

Submission #925147

# Submission time Handle Problem Language Result Execution time Memory
925147 2024-02-10T21:16:48 Z myst6 Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 524288 KB 
#include "happiness.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// segment tree of a[i] - a[i-1] - a[i-2] - ... - a[1]
// maximum of this must be zero or less
// when adding a[i], update range [a[i], a[i]] with +a[i]
// and updating range [a[i]+1,inf] with -a[i]
// and do the opposite when removing

struct Node;

const int sz = 18'000'000;
int nextfree = 1;
vector<Node> nodes(sz);

struct Node {
	ll tag, mx;
	int left, right;
	Node() : tag(0), mx(0), left(0), right(0) {}
	void extend(ll xl, ll xr) {
		if (xl != xr && !left) {
			left = nextfree++;
			right = nextfree++;
		}
	}
	void apply(ll xl, ll xr) {
		extend(xl, xr);
		if (tag != 0) {
			mx += tag;
			if (left) nodes[left].tag += tag;
			if (right) nodes[right].tag += tag;
			tag = 0;
		}
	}
	void update(ll l, ll r, ll xl, ll xr, ll delta) {
		if (l > r) return;
		if (l == xl && r == xr) {
			tag += delta;
		} else {
			apply(xl, xr);
			ll xm = (xl + xr) / 2;
			nodes[left].update(l, min(r, xm), xl, xm, delta);
			nodes[right].update(max(l, xm+1), r, xm+1, xr, delta);
			nodes[left].apply(xl, xm); nodes[right].apply(xm+1, xr);
			mx = max(nodes[left].mx, nodes[right].mx);
		}
	}
} tree;

ll hi = 1'000'000'000'005LL;

unordered_map<ll,int> cnt;

void add(ll coin) {
	cnt[coin] += 1;
	if (cnt[coin] == 1) tree.update(coin, coin, 1, hi, +coin);
	tree.update(coin+1, hi, 1, hi, -coin);
}

void remove(ll coin) {
	cnt[coin] -= 1;
	if (cnt[coin] == 0) tree.update(coin, coin, 1, hi, -coin);
	tree.update(coin+1, hi, 1, hi, +coin);
}

bool check() {
	tree.apply(1, hi);
	return tree.mx <= 1;
}

bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
	hi = maxCoinSize+1;
	cnt.reserve(700'000);
	for (int i=0; i<coinsCount; i++) add(coins[i]);
	return check();
}

bool is_happy(int event, int coinsCount, ll coins[]) {
	for (int i=0; i<coinsCount; i++) 
		if (event == 1) add(coins[i]);
		else remove(coins[i]);
	return check();
}

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 143 ms 428624 KB Output is correct
2 Correct 65 ms 428656 KB Output is correct
3 Correct 66 ms 428552 KB Output is correct
4 Correct 68 ms 428688 KB Output is correct
5 Correct 70 ms 428624 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 428624 KB Output is correct
2 Correct 65 ms 428656 KB Output is correct
3 Correct 66 ms 428552 KB Output is correct
4 Correct 68 ms 428688 KB Output is correct
5 Correct 70 ms 428624 KB Output is correct
6 Correct 76 ms 428700 KB Output is correct
7 Correct 68 ms 428624 KB Output is correct
8 Correct 95 ms 429084 KB Output is correct
9 Correct 99 ms 429140 KB Output is correct
10 Correct 91 ms 429024 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 428624 KB Output is correct
2 Correct 65 ms 428656 KB Output is correct
3 Correct 66 ms 428552 KB Output is correct
4 Correct 68 ms 428688 KB Output is correct
5 Correct 70 ms 428624 KB Output is correct
6 Correct 509 ms 435240 KB Output is correct
7 Correct 540 ms 435220 KB Output is correct
8 Correct 546 ms 435312 KB Output is correct
9 Correct 848 ms 437936 KB Output is correct
10 Correct 894 ms 439376 KB Output is correct
11 Correct 376 ms 439808 KB Output is correct
12 Correct 357 ms 439744 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 428624 KB Output is correct
2 Correct 65 ms 428656 KB Output is correct
3 Correct 66 ms 428552 KB Output is correct
4 Correct 68 ms 428688 KB Output is correct
5 Correct 70 ms 428624 KB Output is correct
6 Correct 76 ms 428700 KB Output is correct
7 Correct 68 ms 428624 KB Output is correct
8 Correct 95 ms 429084 KB Output is correct
9 Correct 99 ms 429140 KB Output is correct
10 Correct 91 ms 429024 KB Output is correct
11 Correct 509 ms 435240 KB Output is correct
12 Correct 540 ms 435220 KB Output is correct
13 Correct 546 ms 435312 KB Output is correct
14 Correct 848 ms 437936 KB Output is correct
15 Correct 894 ms 439376 KB Output is correct
16 Correct 376 ms 439808 KB Output is correct
17 Correct 357 ms 439744 KB Output is correct
18 Correct 1081 ms 436108 KB Output is correct
19 Correct 1079 ms 436208 KB Output is correct
20 Execution timed out 3193 ms 524288 KB Time limit exceeded
21 Halted 0 ms 0 KB -