oj.uz

Submission #871290

# Submission time Handle Problem Language Result Execution time Memory
871290 2023-11-10T13:15:26 Z TAhmed33 Weirdtree (RMI21_weirdtree) C++17
13 / 100
 35 ms 11600 KB 
#include <bits/stdc++.h>
#include <weirdtree.h>
using namespace std;
typedef long long ll;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MAXN = 8e4 + 25;
struct SegmentTree {
	int arr[MAXN]; pair <int, int> tree[2 * MAXN];
	ll sum[2 * MAXN];
	void build (int l, int r, int node) {
		if (l == r) {
			tree[node] = {arr[l], -l};
			sum[node] = arr[l];
		} else {
			build(l, mid, tl); build(mid + 1, r, tr);
			tree[node] = max(tree[tl], tree[tr]);
			sum[node] = sum[tl] + sum[tr];
		}
	}
	void update (int l, int r, int a, int b, int node) {
		if (l > a || r < a) return;
		if (l == r) {
			tree[node] = {b, -l};
			sum[node] = b;
			return;
		}
		update(l, mid, a, b, tl); update(mid + 1, r, a, b, tr);
		tree[node] = max(tree[tl], tree[tr]);
		sum[node] = sum[tl] + sum[tr];
	}
	pair <int, int> get (int l, int r, int a, int b, int node) {
		if (l > b || r < a) return {-1, 0};
		if (l >= a && r <= b) return tree[node];
		return max(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
	}
	ll getsum (int l, int r, int a, int b, int node) {
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return sum[node];
		return getsum(l, mid, a, b, tl) + getsum(mid + 1, r, a, b, tr);
	}
} cur;
int n;
void initialise (int N, int q, int h[]) {
	n = N;
	for (int i = 1; i <= n; i++) cur.arr[i] = h[i];
	cur.build(1, n, 1);
}
void cut (int l, int r, int z) {
	auto x = cur.get(1, n, l, r, 1);
	if (x.first == 0) return;
	x.second *= -1;
	cur.update(1, n, x.second, x.first - 1, 1);
}
void magic (int i, int x) {
	cur.update(1, n, i, x, 1);
}
long long int inspect (int l, int r) {
	return cur.getsum(1, n, l, r, 1);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 33 ms 5940 KB Output is correct
4 Correct 35 ms 5724 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #4
0 / 19.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 11600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 33 ms 5940 KB Output is correct
4 Correct 35 ms 5724 KB Output is correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 33 ms 5940 KB Output is correct
4 Correct 35 ms 5724 KB Output is correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -