Submission #796827

#	Time	Username	Problem	Language	Result	Execution time	Memory
796827		rainboy	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	477 ms	34056 KiB

weirdtree

#include "weirdtree.h"
#include <string.h>

using namespace std;

const int N = 300000, H_ = 19, N_ = 1 << H_;	/* H_ = ceil(log2(N)) */

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

void pus(int i);
void pul(int i);

long long sum[N_ * 2]; int mx1[N_ * 2], kk1[N_ * 2], mx2[N_ * 2], lz[N_], h_, n_;

void put(int i, int x) {
	if (mx1[i] - x == mx2[i]) {
		pus(i), lz[i] += x, pus(i);
		pul(i);
	} else {
		sum[i] -= (long long) x * kk1[i];
		mx1[i] -= x;
		if (i < n_)
			lz[i] += x;
	}
}

void pus(int i) {
	if (lz[i]) {
		int l = i << 1, r = l | 1;
		if (mx1[l] > mx1[r])
			put(l, lz[i]);
		else if (mx1[l] < mx1[r])
			put(r, lz[i]);
		else
			put(l, lz[i]), put(r, lz[i]);
		lz[i] = 0;
	}
}

void pul(int i) {
	if (!lz[i]) {
		int l = i << 1, r = l | 1;
		sum[i] = sum[l] + sum[r];
		if (mx1[l] > mx1[r])
			mx1[i] = mx1[l], kk1[i] = kk1[l], mx2[i] = max(mx2[l], mx1[r]);
		else if (mx1[l] < mx1[r])
			mx1[i] = mx1[r], kk1[i] = kk1[r], mx2[i] = max(mx1[l], mx2[r]);
		else
			mx1[i] = mx1[l], kk1[i] = kk1[l] + kk1[r], mx2[i] = max(mx2[l], mx2[r]);
	}
}

void push(int i) {
	for (int h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void initialise(int n, int q, int *aa) {
	h_ = 0;
	while (1 << h_ < n)
		h_++;
	n_ = 1 << h_;
	memset(lz, 0, n_ * sizeof *lz);
	for (int i = 0; i < n_; i++) {
		int a = i < n ? aa[i + 1] : 0;
		sum[n_ + i] = mx1[n_ + i] = a, kk1[n_ + i] = 1, mx2[n_ + i] = -1;
	}
	for (int i = n_ - 1; i > 0; i--)
		pul(i);
}

int ii[(H_ + 1) * 2], ii_[H_ + 1], cnt, cnt_;

void cut(int l, int r, int x) {
	l--, r--;
	int l_ = l += n_, r_ = r += n_;
	push(l_), push(r_);
	cnt = cnt_ = 0;
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			ii[cnt++] = l++;
		if ((r & 1) == 0)
			ii_[cnt_++] = r--;
	}
	while (cnt_--)
		ii[cnt++] = ii_[cnt_];
	while (1) {
		int a1, k1, a2;
		a1 = 0;
		for (int h = 0; h < cnt; h++) {
			int i = ii[h];
			a1 = max(a1, mx1[i]);
		}
		if (a1 == 0)
			break;
		a2 = 0, k1 = 0;
		for (int h = 0; h < cnt; h++) {
			int i = ii[h];
			if (mx1[i] == a1)
				a2 = max(a2, mx2[i]), k1 += kk1[i];
			else
				a2 = max(a2, mx1[i]);
		}
		if (x / k1 >= a1 - a2) {
			for (int h = 0; h < cnt; h++) {
				int i = ii[h];
				if (mx1[i] == a1)
					put(i, a1 - a2);
			}
			x -= (a1 - a2) * k1;
		} else {
			for (int h = 0; h < cnt; h++) {
				int i = ii[h];
				if (mx1[i] == a1)
					put(i, x / k1);
			}
			a1 -= x / k1, x %= k1;
			for (int h = 0; h < cnt; h++) {
				int i = ii[h];
				if (mx1[i] == a1) {
					if (x >= kk1[i])
						put(i, 1), x -= kk1[i];
					else {
						while (i < n_) {
							pus(i);
							if (mx1[i << 1 | 0] != mx1[i])
								i = i << 1 | 1;
							else if (x >= kk1[i << 1 | 0])
								put(i << 1 | 0, 1), x -= kk1[i << 1 | 0], i = i << 1 | 1;
							else
								i = i << 1 | 0;
						}
						pull(i);
						break;
					}
				}
			}
			break;
		}
	}
	pull(l_), pull(r_);
}

void magic(int i, int a) {
	i--;
	i += n_;
	push(i);
	sum[i] = mx1[i] = a, kk1[i] = 1, mx2[i] = -1;
	pull(i);
}

long long inspect(int l, int r) {
	l--, r--;
	push(l += n_), push(r += n_);
	long long x = 0;
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			x += sum[l++];
		if ((r & 1) == 0)
			x += sum[r--];
	}
	return x;
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 10 / 10
• Subtask 6: 21 / 21
• Subtask 7: 29 / 29