oj.uz

Submission #925146

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

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 124 ms 428492 KB Output is correct
2 Correct 66 ms 428660 KB Output is correct
3 Correct 65 ms 428528 KB Output is correct
4 Correct 67 ms 428660 KB Output is correct
5 Correct 75 ms 428636 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 428492 KB Output is correct
2 Correct 66 ms 428660 KB Output is correct
3 Correct 65 ms 428528 KB Output is correct
4 Correct 67 ms 428660 KB Output is correct
5 Correct 75 ms 428636 KB Output is correct
6 Correct 68 ms 428628 KB Output is correct
7 Correct 68 ms 428592 KB Output is correct
8 Correct 95 ms 429112 KB Output is correct
9 Correct 93 ms 428884 KB Output is correct
10 Correct 95 ms 429352 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 428492 KB Output is correct
2 Correct 66 ms 428660 KB Output is correct
3 Correct 65 ms 428528 KB Output is correct
4 Correct 67 ms 428660 KB Output is correct
5 Correct 75 ms 428636 KB Output is correct
6 Correct 732 ms 435236 KB Output is correct
7 Correct 694 ms 435028 KB Output is correct
8 Correct 722 ms 435356 KB Output is correct
9 Correct 1143 ms 437840 KB Output is correct
10 Correct 1183 ms 439252 KB Output is correct
11 Correct 676 ms 440020 KB Output is correct
12 Correct 593 ms 439816 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 428492 KB Output is correct
2 Correct 66 ms 428660 KB Output is correct
3 Correct 65 ms 428528 KB Output is correct
4 Correct 67 ms 428660 KB Output is correct
5 Correct 75 ms 428636 KB Output is correct
6 Correct 68 ms 428628 KB Output is correct
7 Correct 68 ms 428592 KB Output is correct
8 Correct 95 ms 429112 KB Output is correct
9 Correct 93 ms 428884 KB Output is correct
10 Correct 95 ms 429352 KB Output is correct
11 Correct 732 ms 435236 KB Output is correct
12 Correct 694 ms 435028 KB Output is correct
13 Correct 722 ms 435356 KB Output is correct
14 Correct 1143 ms 437840 KB Output is correct
15 Correct 1183 ms 439252 KB Output is correct
16 Correct 676 ms 440020 KB Output is correct
17 Correct 593 ms 439816 KB Output is correct
18 Correct 1079 ms 436308 KB Output is correct
19 Correct 1074 ms 436200 KB Output is correct
20 Execution timed out 3138 ms 524288 KB Time limit exceeded
21 Halted 0 ms 0 KB -