oj.uz

Submission #645479

# Submission time Handle Problem Language Result Execution time Memory
645479 2022-09-27T08:18:05 Z Vanilla Weirdtree (RMI21_weirdtree) C++17
13 / 100
 81 ms 13356 KB 
#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
typedef long long int64;

const int maxn = 8e4;
struct node {
	int64 v = 0;
	int64 mx = -1;
	int64 mxpos = 0;

	const node operator+ (const node& oth) const {
		node nw;
		nw.v = v + oth.v;
		if (mx >= oth.mx) {
			nw.mx = mx;
			nw.mxpos = mxpos;
		}
		else {
			nw.mx = oth.mx;
			nw.mxpos = oth.mxpos;
		}
		return nw;
	}
} sgt [4 * maxn];

node upd (int x, int l, int r, int pos, int64 v) {
	if (l > pos || r < pos) return sgt[x];
	if (l == pos && r == pos) {
		sgt[x].v = sgt[x].mx = v;
		sgt[x].mxpos = pos;
		return sgt[x];
	}
	int mid = (l + r) / 2;
	return sgt[x] = upd(x * 2, l, mid, pos, v) + upd(x * 2 + 1, mid + 1, r, pos, v);
}

node query (int x, int l, int r, int il, int ir) {
	if (l > ir || r < il) return node();
	if (il <= l && r <= ir) return sgt[x];
	int mid = (l + r) / 2;
	return query(x * 2, l, mid, il, ir) + query(x * 2 + 1, mid + 1, r, il, ir);
}

int n;

void initialise(int N, int Q, int h[]) {
	n = N;
	for (int i = 1; i <= N; i++){
		upd(1, 1, N, i, h[i]);
	}
}
void cut(int l, int r, int k) {
	node q = query(1, 1, n, l, r);
	if (q.mx) {
		upd(1, 1, n, q.mxpos, q.mx - 1);
	}
}
void magic(int i, int x) {
	upd(1, 1, n, i, x);
}
int64 inspect(int l, int r) {
	return query(1, 1, n, l, r).v;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 81 ms 9168 KB Output is correct
4 Correct 79 ms 9132 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 340 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 14 ms 13356 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 81 ms 9168 KB Output is correct
4 Correct 79 ms 9132 KB Output is correct
5 Incorrect 1 ms 340 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 81 ms 9168 KB Output is correct
4 Correct 79 ms 9132 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -