oj.uz

Submission #796827

# Submission time Handle Problem Language Result Execution time Memory
796827 2023-07-28T19:24:42 Z rainboy Weirdtree (RMI21_weirdtree) C++17
100 / 100
 477 ms 34056 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 47 ms 7388 KB Output is correct
4 Correct 51 ms 7424 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 314 ms 33996 KB Output is correct
4 Correct 305 ms 34056 KB Output is correct
5 Correct 302 ms 33976 KB Output is correct
6 Correct 282 ms 33848 KB Output is correct
7 Correct 455 ms 8420 KB Output is correct
8 Correct 212 ms 8156 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 8420 KB Output is correct
2 Correct 212 ms 8156 KB Output is correct
3 Correct 477 ms 26584 KB Output is correct
4 Correct 462 ms 32848 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 47 ms 7388 KB Output is correct
4 Correct 51 ms 7424 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 455 ms 8420 KB Output is correct
8 Correct 212 ms 8156 KB Output is correct
9 Correct 45 ms 8664 KB Output is correct
10 Correct 50 ms 8720 KB Output is correct
11 Correct 46 ms 8648 KB Output is correct
12 Correct 50 ms 8812 KB Output is correct
13 Correct 46 ms 8788 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 47 ms 7388 KB Output is correct
4 Correct 51 ms 7424 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 314 ms 33996 KB Output is correct
8 Correct 305 ms 34056 KB Output is correct
9 Correct 302 ms 33976 KB Output is correct
10 Correct 282 ms 33848 KB Output is correct
11 Correct 477 ms 26584 KB Output is correct
12 Correct 462 ms 32848 KB Output is correct
13 Correct 45 ms 8664 KB Output is correct
14 Correct 50 ms 8720 KB Output is correct
15 Correct 46 ms 8648 KB Output is correct
16 Correct 50 ms 8812 KB Output is correct
17 Correct 46 ms 8788 KB Output is correct
18 Correct 455 ms 8420 KB Output is correct
19 Correct 212 ms 8156 KB Output is correct
20 Correct 226 ms 33192 KB Output is correct
21 Correct 259 ms 33664 KB Output is correct
22 Correct 220 ms 33384 KB Output is correct
23 Correct 267 ms 33392 KB Output is correct
24 Correct 213 ms 33340 KB Output is correct