oj.uz

Submission #925143

# Submission time Handle Problem Language Result Execution time Memory
925143 2024-02-10T21:05:20 Z myst6 Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1094 ms 496716 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 = 10'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;

const 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[]) {
	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 75 ms 240692 KB Output is correct
2 Correct 39 ms 240720 KB Output is correct
3 Correct 39 ms 240840 KB Output is correct
4 Correct 39 ms 240844 KB Output is correct
5 Correct 39 ms 240720 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 240692 KB Output is correct
2 Correct 39 ms 240720 KB Output is correct
3 Correct 39 ms 240840 KB Output is correct
4 Correct 39 ms 240844 KB Output is correct
5 Correct 39 ms 240720 KB Output is correct
6 Correct 44 ms 240724 KB Output is correct
7 Correct 45 ms 240708 KB Output is correct
8 Correct 71 ms 241240 KB Output is correct
9 Correct 65 ms 241232 KB Output is correct
10 Correct 61 ms 241144 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 240692 KB Output is correct
2 Correct 39 ms 240720 KB Output is correct
3 Correct 39 ms 240840 KB Output is correct
4 Correct 39 ms 240844 KB Output is correct
5 Correct 39 ms 240720 KB Output is correct
6 Correct 723 ms 247516 KB Output is correct
7 Correct 669 ms 247500 KB Output is correct
8 Correct 698 ms 247276 KB Output is correct
9 Correct 1094 ms 250208 KB Output is correct
10 Correct 1091 ms 251540 KB Output is correct
11 Correct 579 ms 251988 KB Output is correct
12 Correct 568 ms 251808 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 240692 KB Output is correct
2 Correct 39 ms 240720 KB Output is correct
3 Correct 39 ms 240840 KB Output is correct
4 Correct 39 ms 240844 KB Output is correct
5 Correct 39 ms 240720 KB Output is correct
6 Correct 44 ms 240724 KB Output is correct
7 Correct 45 ms 240708 KB Output is correct
8 Correct 71 ms 241240 KB Output is correct
9 Correct 65 ms 241232 KB Output is correct
10 Correct 61 ms 241144 KB Output is correct
11 Correct 723 ms 247516 KB Output is correct
12 Correct 669 ms 247500 KB Output is correct
13 Correct 698 ms 247276 KB Output is correct
14 Correct 1094 ms 250208 KB Output is correct
15 Correct 1091 ms 251540 KB Output is correct
16 Correct 579 ms 251988 KB Output is correct
17 Correct 568 ms 251808 KB Output is correct
18 Runtime error 716 ms 496716 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -