oj.uz

Submission #925142

# Submission time Handle Problem Language Result Execution time Memory
925142 2024-02-10T21:01:12 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;

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

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);
		cnt.erase(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[]) {
	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 68 ms 423248 KB Output is correct
2 Correct 65 ms 422996 KB Output is correct
3 Correct 64 ms 422992 KB Output is correct
4 Correct 64 ms 423112 KB Output is correct
5 Correct 65 ms 423032 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 423248 KB Output is correct
2 Correct 65 ms 422996 KB Output is correct
3 Correct 64 ms 422992 KB Output is correct
4 Correct 64 ms 423112 KB Output is correct
5 Correct 65 ms 423032 KB Output is correct
6 Correct 66 ms 423144 KB Output is correct
7 Correct 67 ms 423040 KB Output is correct
8 Correct 96 ms 423808 KB Output is correct
9 Correct 94 ms 423760 KB Output is correct
10 Correct 93 ms 424032 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 423248 KB Output is correct
2 Correct 65 ms 422996 KB Output is correct
3 Correct 64 ms 422992 KB Output is correct
4 Correct 64 ms 423112 KB Output is correct
5 Correct 65 ms 423032 KB Output is correct
6 Correct 851 ms 430416 KB Output is correct
7 Correct 831 ms 430560 KB Output is correct
8 Correct 894 ms 430264 KB Output is correct
9 Correct 1344 ms 430160 KB Output is correct
10 Correct 1511 ms 433292 KB Output is correct
11 Correct 728 ms 435832 KB Output is correct
12 Correct 715 ms 436060 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 423248 KB Output is correct
2 Correct 65 ms 422996 KB Output is correct
3 Correct 64 ms 422992 KB Output is correct
4 Correct 64 ms 423112 KB Output is correct
5 Correct 65 ms 423032 KB Output is correct
6 Correct 66 ms 423144 KB Output is correct
7 Correct 67 ms 423040 KB Output is correct
8 Correct 96 ms 423808 KB Output is correct
9 Correct 94 ms 423760 KB Output is correct
10 Correct 93 ms 424032 KB Output is correct
11 Correct 851 ms 430416 KB Output is correct
12 Correct 831 ms 430560 KB Output is correct
13 Correct 894 ms 430264 KB Output is correct
14 Correct 1344 ms 430160 KB Output is correct
15 Correct 1511 ms 433292 KB Output is correct
16 Correct 728 ms 435832 KB Output is correct
17 Correct 715 ms 436060 KB Output is correct
18 Correct 1247 ms 430608 KB Output is correct
19 Correct 1214 ms 430160 KB Output is correct
20 Execution timed out 2060 ms 524288 KB Time limit exceeded
21 Halted 0 ms 0 KB -