oj.uz

Submission #1035373

# Submission time Handle Problem Language Result Execution time Memory
1035373 2024-07-26T10:00:21 Z andrei_c1 Weirdtree (RMI21_weirdtree) C++17
100 / 100
 1048 ms 40628 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 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 600 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 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 153 ms 10448 KB Output is correct
4 Correct 142 ms 10476 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1048 ms 40180 KB Output is correct
4 Correct 922 ms 40628 KB Output is correct
5 Correct 1042 ms 39380 KB Output is correct
6 Correct 934 ms 39036 KB Output is correct
7 Correct 125 ms 10576 KB Output is correct
8 Correct 156 ms 10332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 10576 KB Output is correct
2 Correct 156 ms 10332 KB Output is correct
3 Correct 346 ms 37308 KB Output is correct
4 Correct 428 ms 38736 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 153 ms 10448 KB Output is correct
4 Correct 142 ms 10476 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 125 ms 10576 KB Output is correct
8 Correct 156 ms 10332 KB Output is correct
9 Correct 155 ms 10576 KB Output is correct
10 Correct 147 ms 10324 KB Output is correct
11 Correct 149 ms 10324 KB Output is correct
12 Correct 143 ms 10832 KB Output is correct
13 Correct 144 ms 10836 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 153 ms 10448 KB Output is correct
4 Correct 142 ms 10476 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1048 ms 40180 KB Output is correct
8 Correct 922 ms 40628 KB Output is correct
9 Correct 1042 ms 39380 KB Output is correct
10 Correct 934 ms 39036 KB Output is correct
11 Correct 346 ms 37308 KB Output is correct
12 Correct 428 ms 38736 KB Output is correct
13 Correct 155 ms 10576 KB Output is correct
14 Correct 147 ms 10324 KB Output is correct
15 Correct 149 ms 10324 KB Output is correct
16 Correct 143 ms 10832 KB Output is correct
17 Correct 144 ms 10836 KB Output is correct
18 Correct 125 ms 10576 KB Output is correct
19 Correct 156 ms 10332 KB Output is correct
20 Correct 659 ms 37456 KB Output is correct
21 Correct 734 ms 40008 KB Output is correct
22 Correct 676 ms 39508 KB Output is correct
23 Correct 742 ms 39508 KB Output is correct
24 Correct 696 ms 38736 KB Output is correct