oj.uz

Submission #1035553

# Submission time Handle Problem Language Result Execution time Memory
1035553 2024-07-26T11:51:22 Z andrei_c1 Weirdtree (RMI21_weirdtree) C++17
100 / 100
 286 ms 40836 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(-kInf), frq(0) {}
	node_t(int val) : sum(val), mx1(val), mx2(-kInf), 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 &extra, int val, int node, int l, int r) {
		if(tree[node].mx1 <= val - (extra > 0)) {
			return;
		}
		if(a <= l && r <= b && tree[node].mx2 < val - (extra > 0) && (extra == 0 || extra >= tree[node].frq)) {
			tree[node].update(val - (extra > 0));
			if(extra > 0) {
				extra -= tree[node].frq;
			}
		} else {
			push(node);
			int mid = (l + r) >> 1;
			if(a <= mid) {
				update(a, b, extra, val, node << 1, l, mid);
			}
			if(b > mid) {
				update(a, b, extra, val, node << 1 | 1, mid + 1, r);
			}
			tree[node] = tree[node << 1] + tree[node << 1 | 1];
		}
	}
	void update(int a, int b, int extra, int val) {
		update(a, b, extra, 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;
		}
		maxSelf(ans.mx2, 0);
		ll cuts = (ll)(ans.mx1 - ans.mx2) * ans.frq;
		if(cuts <= k) {
			ds.update(ql, qr, 0, ans.mx2);
			k -= cuts;
		} else {
			ds.update(ql, qr, k % ans.frq, ans.mx1 - 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 48 ms 10568 KB Output is correct
4 Correct 49 ms 10324 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 3 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 3 ms 604 KB Output is correct
3 Correct 286 ms 40072 KB Output is correct
4 Correct 273 ms 40836 KB Output is correct
5 Correct 275 ms 39512 KB Output is correct
6 Correct 277 ms 38928 KB Output is correct
7 Correct 7 ms 10588 KB Output is correct
8 Correct 44 ms 10332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10588 KB Output is correct
2 Correct 44 ms 10332 KB Output is correct
3 Correct 80 ms 37468 KB Output is correct
4 Correct 93 ms 38896 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 48 ms 10568 KB Output is correct
4 Correct 49 ms 10324 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 7 ms 10588 KB Output is correct
8 Correct 44 ms 10332 KB Output is correct
9 Correct 47 ms 10576 KB Output is correct
10 Correct 56 ms 10404 KB Output is correct
11 Correct 47 ms 10104 KB Output is correct
12 Correct 48 ms 10832 KB Output is correct
13 Correct 46 ms 10836 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 48 ms 10568 KB Output is correct
4 Correct 49 ms 10324 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 286 ms 40072 KB Output is correct
8 Correct 273 ms 40836 KB Output is correct
9 Correct 275 ms 39512 KB Output is correct
10 Correct 277 ms 38928 KB Output is correct
11 Correct 80 ms 37468 KB Output is correct
12 Correct 93 ms 38896 KB Output is correct
13 Correct 47 ms 10576 KB Output is correct
14 Correct 56 ms 10404 KB Output is correct
15 Correct 47 ms 10104 KB Output is correct
16 Correct 48 ms 10832 KB Output is correct
17 Correct 46 ms 10836 KB Output is correct
18 Correct 7 ms 10588 KB Output is correct
19 Correct 44 ms 10332 KB Output is correct
20 Correct 220 ms 37548 KB Output is correct
21 Correct 262 ms 39940 KB Output is correct
22 Correct 269 ms 39504 KB Output is correct
23 Correct 246 ms 39408 KB Output is correct
24 Correct 240 ms 38564 KB Output is correct