oj.uz

Submission #1035390

# Submission time Handle Problem Language Result Execution time Memory
1035390 2024-07-26T10:10:56 Z andrei_c1 Weirdtree (RMI21_weirdtree) C++17
100 / 100
 1151 ms 33200 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct node_t {
	ll sum;
	int mx1, mx2, frq;
	node_t() : sum(0), mx1(0), mx2(0), frq(0) {}
	node_t(int val) : sum(val), mx1(val), mx2(0), frq(1) {}
	node_t operator + (const node_t &oth) const {
		node_t res;
		res.sum = sum + oth.sum;
		if(mx1 > oth.mx1) {
			res.mx1 = mx1;
			res.mx2 = max(mx2, oth.mx1);
			res.frq = frq;
		} else if(mx1 < oth.mx1) {
			res.mx1 = oth.mx1;
			res.mx2 = max(mx1, oth.mx2);
			res.frq = oth.frq;
		} else {
			res.mx1 = mx1;
			res.mx2 = max(mx2, oth.mx2);
			res.frq = frq + oth.frq;
		}
		return res;
	}
	void update(int val) {
		sum += (ll)(val - mx1) * frq;
		mx1 = val;
	}
};

vector<int> a;

struct aint {
	int n;
	vector<node_t> tree;
	aint() {}
	aint(int n) : n(n), tree(n << 2 | 1) {}
	void build(int node, int l, int r) {
		if(l == r) {
			tree[node] = node_t(a[l]);
		} else {
			int mid = (l + r) >> 1;
			build(node << 1, l, mid);
			build(node << 1 | 1, mid + 1, r);
			tree[node] = tree[node << 1] + tree[node << 1 | 1];
		}
	}
	void build() {
		build(1, 1, n);
	}
	void push(int node) {
		for(const auto &it : {node << 1, node << 1 | 1}) if(it <= 4 * n) {
			if(tree[node].mx1 < tree[it].mx1) {
				tree[it].update(tree[node].mx1);
			}
		}
	}
	void update(int a, int b, int val, int node, int l, int r) {
		if(tree[node].mx1 <= val) {
			return;
		}
		if(a <= l && r <= b && tree[node].mx2 < val) {
			tree[node].update(val);
		} else {
			push(node);
			int mid = (l + r) >> 1;
			if(a <= mid) {
				update(a, b, val, node << 1, l, mid);
			}
			if(b > mid) {
				update(a, b, val, node << 1 | 1, mid + 1, r);
			}
			tree[node] = tree[node << 1] + tree[node << 1 | 1];
		}
	}
	void update(int a, int b, int val) {
		update(a, b, val, 1, 1, n);
	}
	void update(int p, int val, int node, int l, int r) {
		if(l == r) {
			tree[node] = node_t(val);
		} else {
			push(node);
			int mid = (l + r) >> 1;
			if(p <= mid) {
				update(p, val, node << 1, l, mid);
			} else {
				update(p, val, node << 1 | 1, mid + 1, r);
			}
			tree[node] = tree[node << 1] + tree[node << 1 | 1];
		}
	}
	void update(int p, int val) {
		update(p, val, 1, 1, n);
	}
	node_t query(int a, int b, int node, int l, int r) {
		if(a <= l && r <= b) {
			return tree[node];
		} else {
			push(node);
			int mid = (l + r) >> 1;
			node_t lhs, rhs;
			if(a <= mid) {
				lhs = query(a, b, node << 1, l, mid);
			}
			if(b > mid) {
				rhs = query(a, b, node << 1 | 1, mid + 1, r);
			}
			return lhs + rhs;
		}
	}
	node_t query(int a, int b) {
		return query(a, b, 1, 1, n);
	}
} ds;

void initialise(int n, int q, int h[]) {
	a = vector<int>(n + 1);
	for(int i = 1; i <= n; i++) {
		a[i] = h[i];
	}
	ds = aint(n);
	ds.build();
}

void cut(int ql, int qr, int k) {
	while(k > 0) {
		node_t ans = ds.query(ql, qr);
		if(ans.mx1 == 0) {
			return;
		}
		ll cuts = (ll)(ans.mx1 - ans.mx2) * ans.frq;
		if(cuts <= k) {
			ds.update(ql, qr, ans.mx2);
			k -= cuts;
		} else {
			int extra = k % ans.frq, l = ql, r = qr, mid;
			while(l <= r) {
				mid = (l + r) >> 1;
				node_t res = ds.query(ql, mid);
				if(res.mx1 < ans.mx1 || (res.mx1 == ans.mx1 && res.frq <= extra)) {
					l = mid + 1;
				} else {
					r = mid - 1;
				}
			}
			ds.update(ql, qr, ans.mx1 - k / ans.frq);
			if(ql <= l - 1) {
				ds.update(ql, l - 1, ans.mx1 - 1 - k / ans.frq);
			}
			k = 0;
		}
	}
}

void magic(int i, int x) {
	ds.update(i, x);
}

ll inspect(int l, int r) {
	return ds.query(l, r).sum;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 194 ms 8564 KB Output is correct
4 Correct 173 ms 8532 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 1151 ms 32584 KB Output is correct
4 Correct 954 ms 33200 KB Output is correct
5 Correct 1112 ms 31828 KB Output is correct
6 Correct 947 ms 31568 KB Output is correct
7 Correct 135 ms 8540 KB Output is correct
8 Correct 159 ms 8648 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 8540 KB Output is correct
2 Correct 159 ms 8648 KB Output is correct
3 Correct 365 ms 30548 KB Output is correct
4 Correct 460 ms 31824 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 194 ms 8564 KB Output is correct
4 Correct 173 ms 8532 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 135 ms 8540 KB Output is correct
8 Correct 159 ms 8648 KB Output is correct
9 Correct 178 ms 8528 KB Output is correct
10 Correct 153 ms 8276 KB Output is correct
11 Correct 165 ms 8272 KB Output is correct
12 Correct 160 ms 8792 KB Output is correct
13 Correct 160 ms 9044 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 194 ms 8564 KB Output is correct
4 Correct 173 ms 8532 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 1151 ms 32584 KB Output is correct
8 Correct 954 ms 33200 KB Output is correct
9 Correct 1112 ms 31828 KB Output is correct
10 Correct 947 ms 31568 KB Output is correct
11 Correct 365 ms 30548 KB Output is correct
12 Correct 460 ms 31824 KB Output is correct
13 Correct 178 ms 8528 KB Output is correct
14 Correct 153 ms 8276 KB Output is correct
15 Correct 165 ms 8272 KB Output is correct
16 Correct 160 ms 8792 KB Output is correct
17 Correct 160 ms 9044 KB Output is correct
18 Correct 135 ms 8540 KB Output is correct
19 Correct 159 ms 8648 KB Output is correct
20 Correct 750 ms 29992 KB Output is correct
21 Correct 761 ms 32336 KB Output is correct
22 Correct 650 ms 31740 KB Output is correct
23 Correct 767 ms 31576 KB Output is correct
24 Correct 730 ms 30864 KB Output is correct