Submission #719435

#	Time	Username	Problem	Language	Result	Execution time	Memory
719435		rainboy	Happiness (Balkan15_HAPPINESS)	C++17	100 / 100	1130 ms	22960 KiB

happiness

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40