oj.uz

Submission #1034787

# Submission time Handle Problem Language Result Execution time Memory
1034787 2024-07-25T18:17:10 Z andrei_c1 Weirdtree (RMI21_weirdtree) C++17
5 / 100
 401 ms 37460 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;
		}
		int cuts = (ans.mx1 - ans.mx2) * ans.frq;
		if(cuts <= k) {
			ds.update(ql, qr, max(ans.mx2, 0));
			k -= cuts;
		} else {
			int rem = k % ans.frq, l = ql, r = qr, mid;
			while(l <= r) {
				mid = (l + r) >> 1;
				node_t res = ds.query(ql, mid);
				if(res.frq <= rem) {
					l = mid + 1;
				} else {
					r = mid - 1;
				}
			}
			if(ql <= l - 1) {
				ds.update(ql, l - 1, max(ans.mx1 - 1 - k / ans.frq, 0));
			}
			ds.update(ql, qr, max(ans.mx1 - k / ans.frq, 0));
			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
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 139 ms 10576 KB Output is correct
4 Incorrect 143 ms 10320 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 401 ms 37460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
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 139 ms 10576 KB Output is correct
4 Incorrect 143 ms 10320 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
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 139 ms 10576 KB Output is correct
4 Incorrect 143 ms 10320 KB Output isn't correct
5 Halted 0 ms 0 KB -