Submission #1049263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049263		rainboy	A Light Inconvenience (CEOI23_light)	C++17	100 / 100	311 ms	600 KiB

light

#include "light.h"
#include <cstring>
#include <vector>

using namespace std;

const int N = 150;

typedef vector<long long> vl;
typedef pair<long long, vl> plvl;

long long xx[N], xx_[N]; int n, n_;

void prepare() {
	n = 0;
	xx[n++] = 1;
}

void update(long long d) {
	for (int i = 0; i < n; i++)
		xx[i] += d;
	n_ = 0;
	xx_[n_++] = 1;
	for (int i = 0; i < n; i++) {
		if (xx[i] <= xx_[n_ - 1])
			continue;
		long long x;
		while ((x = xx_[n_ - 1] * 2 + 1) < xx[i]) {
			while (n_ >= 2 && xx_[n_ - 2] * 2 + 1 >= x)
				n_--;
			xx_[n_++] = x;
		}
		x = xx[i];
		while (n_ >= 2 && xx_[n_ - 2] * 2 + 1 >= x)
			n_--;
		xx_[n_++] = x;
	}
	memcpy(xx, xx_, (n = n_) * sizeof *xx_);
}

vl query() {
	vl aa(n);
	for (int i = 0; i < n; i++)
		aa[i] = xx[n - 1] - xx[n - 1 - i] + 1;
	return aa;
}

plvl join(long long d) {
	update(d);
	return { d, query() };
}

plvl leave(long long d) {
	update(-d);
	return { d, query() };
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 5 / 5
• Subtask 7: 60 / 60