oj.uz

Submission #1035382

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

const int kInf = 1e9;

void maxSelf(int &x, int y) {
	if(y > x) {
		x = y;
	}
}

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 res;
			if(a <= mid) {
				res = query(a, b, node << 1, l, mid);
			}
			if(b > mid) {
				res = res + query(a, b, node << 1 | 1, mid + 1, r);
			}
			return res;
		}
	}
	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 604 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 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 175 ms 10616 KB Output is correct
4 Correct 140 ms 10320 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 1133 ms 40172 KB Output is correct
4 Correct 986 ms 40796 KB Output is correct
5 Correct 1048 ms 39508 KB Output is correct
6 Correct 989 ms 38992 KB Output is correct
7 Correct 132 ms 10576 KB Output is correct
8 Correct 176 ms 10316 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 10576 KB Output is correct
2 Correct 176 ms 10316 KB Output is correct
3 Correct 359 ms 37460 KB Output is correct
4 Correct 445 ms 38832 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 175 ms 10616 KB Output is correct
4 Correct 140 ms 10320 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 132 ms 10576 KB Output is correct
8 Correct 176 ms 10316 KB Output is correct
9 Correct 170 ms 10400 KB Output is correct
10 Correct 156 ms 10324 KB Output is correct
11 Correct 167 ms 10324 KB Output is correct
12 Correct 157 ms 10820 KB Output is correct
13 Correct 165 ms 10968 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 175 ms 10616 KB Output is correct
4 Correct 140 ms 10320 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 1133 ms 40172 KB Output is correct
8 Correct 986 ms 40796 KB Output is correct
9 Correct 1048 ms 39508 KB Output is correct
10 Correct 989 ms 38992 KB Output is correct
11 Correct 359 ms 37460 KB Output is correct
12 Correct 445 ms 38832 KB Output is correct
13 Correct 170 ms 10400 KB Output is correct
14 Correct 156 ms 10324 KB Output is correct
15 Correct 167 ms 10324 KB Output is correct
16 Correct 157 ms 10820 KB Output is correct
17 Correct 165 ms 10968 KB Output is correct
18 Correct 132 ms 10576 KB Output is correct
19 Correct 176 ms 10316 KB Output is correct
20 Correct 764 ms 37464 KB Output is correct
21 Correct 800 ms 39904 KB Output is correct
22 Correct 694 ms 39248 KB Output is correct
23 Correct 777 ms 39252 KB Output is correct
24 Correct 722 ms 38480 KB Output is correct