oj.uz

Submission #719435

# Submission time Handle Problem Language Result Execution time Memory
719435 2023-04-05T22:36:12 Z rainboy Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1130 ms 22960 KB 
#include "happiness.h"

const int N = 200000, Q = 100000, K = 5, N_ = N + Q * K + 1;
const long long A = 1000000000001;

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int zz[N_], ll[N_], rr[N_], cc[N_], u_, l_, r_; long long xx[N_], ss[N_], dd[N_];

int node(long long x, int c) {
	static int _ = 1;
	zz[_] = rand_();
	xx[_] = x, cc[_] = c;
	ss[_] = x <= A / c ? x * c : A;
	dd[_] = x;
	return _++;
}

void pul(int u) {
	int l = ll[u], r = rr[u], c = cc[u];
	long long x = xx[u], y = x <= A / c ? x * c : A;
	ss[u] = min(min(ss[l] + y, A) + ss[r], A);
	dd[u] = max(max(dd[l], x - ss[l]), dd[r] - min(ss[l] + y, A));
}

void split(int u, long long x) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (xx[u] < x) {
		split(rr[u], x);
		rr[u] = l_, l_ = u;
	} else if (xx[u] > x) {
		split(ll[u], x);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
	pul(u);
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v), pul(u);
		return u;
	} else {
		ll[v] = merge(u, ll[v]), pul(v);
		return v;
	}
}

void tr_add(long long x) {
	split(u_, x);
	if (u_ == 0)
		u_ = node(x, 1);
	else
		cc[u_]++, pul(u_);
	u_ = merge(merge(l_, u_), r_);
}

void tr_remove(long long x) {
	split(u_, x);
	if (cc[u_] == 1)
		u_ = 0;
	else
		cc[u_]--, pul(u_);
	u_ = merge(merge(l_, u_), r_);
}

bool init(int n, long long m, long long *cc) {
	u_ = 0;
	for (int i = 0; i < n; i++)
		tr_add(cc[i]);
	return dd[u_] <= 1;
}

bool is_happy(int type, int n, long long *cc) {
	for (int i = 0; i < n; i++)
		if (type == 1)
			tr_add(cc[i]);
		else
			tr_remove(cc[i]);
	return dd[u_] <= 1;
}

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 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 14 ms 980 KB Output is correct
9 Correct 14 ms 952 KB Output is correct
10 Correct 13 ms 1052 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 405 ms 11944 KB Output is correct
7 Correct 384 ms 11852 KB Output is correct
8 Correct 389 ms 12144 KB Output is correct
9 Correct 727 ms 17452 KB Output is correct
10 Correct 1130 ms 18764 KB Output is correct
11 Correct 347 ms 17984 KB Output is correct
12 Correct 340 ms 17992 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 14 ms 980 KB Output is correct
9 Correct 14 ms 952 KB Output is correct
10 Correct 13 ms 1052 KB Output is correct
11 Correct 405 ms 11944 KB Output is correct
12 Correct 384 ms 11852 KB Output is correct
13 Correct 389 ms 12144 KB Output is correct
14 Correct 727 ms 17452 KB Output is correct
15 Correct 1130 ms 18764 KB Output is correct
16 Correct 347 ms 17984 KB Output is correct
17 Correct 340 ms 17992 KB Output is correct
18 Correct 531 ms 14584 KB Output is correct
19 Correct 480 ms 14920 KB Output is correct
20 Correct 1049 ms 22960 KB Output is correct
21 Correct 472 ms 13480 KB Output is correct
22 Correct 353 ms 19920 KB Output is correct
23 Correct 355 ms 20380 KB Output is correct
24 Correct 459 ms 14436 KB Output is correct