oj.uz

Submission #925140

# Submission time Handle Problem Language Result Execution time Memory
925140 2024-02-10T20:56:41 Z myst6 Happiness (Balkan15_HAPPINESS) C++14
10 / 100
 216 ms 60944 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 = 1'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);
	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 5 ms 23896 KB Output is correct
2 Correct 5 ms 23896 KB Output is correct
3 Correct 6 ms 23900 KB Output is correct
4 Correct 5 ms 23900 KB Output is correct
5 Correct 5 ms 23932 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23896 KB Output is correct
2 Correct 5 ms 23896 KB Output is correct
3 Correct 6 ms 23900 KB Output is correct
4 Correct 5 ms 23900 KB Output is correct
5 Correct 5 ms 23932 KB Output is correct
6 Correct 7 ms 23900 KB Output is correct
7 Correct 7 ms 23980 KB Output is correct
8 Runtime error 42 ms 49380 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23896 KB Output is correct
2 Correct 5 ms 23896 KB Output is correct
3 Correct 6 ms 23900 KB Output is correct
4 Correct 5 ms 23900 KB Output is correct
5 Correct 5 ms 23932 KB Output is correct
6 Runtime error 216 ms 60944 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23896 KB Output is correct
2 Correct 5 ms 23896 KB Output is correct
3 Correct 6 ms 23900 KB Output is correct
4 Correct 5 ms 23900 KB Output is correct
5 Correct 5 ms 23932 KB Output is correct
6 Correct 7 ms 23900 KB Output is correct
7 Correct 7 ms 23980 KB Output is correct
8 Runtime error 42 ms 49380 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -