oj.uz

Submission #925141

# Submission time Handle Problem Language Result Execution time Memory
925141 2024-02-10T20:57:42 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 = 20'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 161 ms 470392 KB Output is correct
2 Correct 72 ms 469864 KB Output is correct
3 Correct 72 ms 470100 KB Output is correct
4 Correct 72 ms 470100 KB Output is correct
5 Correct 71 ms 470072 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 470392 KB Output is correct
2 Correct 72 ms 469864 KB Output is correct
3 Correct 72 ms 470100 KB Output is correct
4 Correct 72 ms 470100 KB Output is correct
5 Correct 71 ms 470072 KB Output is correct
6 Correct 74 ms 469984 KB Output is correct
7 Correct 73 ms 470008 KB Output is correct
8 Correct 102 ms 470776 KB Output is correct
9 Correct 103 ms 470616 KB Output is correct
10 Correct 96 ms 470808 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 470392 KB Output is correct
2 Correct 72 ms 469864 KB Output is correct
3 Correct 72 ms 470100 KB Output is correct
4 Correct 72 ms 470100 KB Output is correct
5 Correct 71 ms 470072 KB Output is correct
6 Correct 871 ms 482388 KB Output is correct
7 Correct 887 ms 482116 KB Output is correct
8 Correct 909 ms 482364 KB Output is correct
9 Correct 1496 ms 487716 KB Output is correct
10 Correct 1534 ms 490252 KB Output is correct
11 Correct 716 ms 492116 KB Output is correct
12 Correct 709 ms 492116 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 470392 KB Output is correct
2 Correct 72 ms 469864 KB Output is correct
3 Correct 72 ms 470100 KB Output is correct
4 Correct 72 ms 470100 KB Output is correct
5 Correct 71 ms 470072 KB Output is correct
6 Correct 74 ms 469984 KB Output is correct
7 Correct 73 ms 470008 KB Output is correct
8 Correct 102 ms 470776 KB Output is correct
9 Correct 103 ms 470616 KB Output is correct
10 Correct 96 ms 470808 KB Output is correct
11 Correct 871 ms 482388 KB Output is correct
12 Correct 887 ms 482116 KB Output is correct
13 Correct 909 ms 482364 KB Output is correct
14 Correct 1496 ms 487716 KB Output is correct
15 Correct 1534 ms 490252 KB Output is correct
16 Correct 716 ms 492116 KB Output is correct
17 Correct 709 ms 492116 KB Output is correct
18 Correct 1302 ms 489064 KB Output is correct
19 Correct 1280 ms 489796 KB Output is correct
20 Execution timed out 3529 ms 524288 KB Time limit exceeded
21 Halted 0 ms 0 KB -