oj.uz

Submission #597803

# Submission time Handle Problem Language Result Execution time Memory
597803 2022-07-16T22:53:04 Z pedroslrey Weirdtree (RMI21_weirdtree) C++17
13 / 100
 2000 ms 30160 KB 
#include <bits/stdc++.h>
#include "weirdtree.h"

using namespace std;
using lli = long long;

struct node {
	int mx, idx;
	lli sum;

	node (int x = 0, int i = 0, lli s = 0) : mx {x}, idx {i}, sum {s} { }

	node operator+(node other) {
		if (mx > other.mx) return node(mx, idx, sum + other.sum);
		if (mx < other.mx) return node(other.mx, other.idx, sum + other.sum);
		return node(mx, min(idx, other.idx), sum + other.sum);
	}
};

const int MAXN = 3e5 + 10;

int n;
int xs[MAXN];
node seg[4*MAXN];

node query(int pos, int ini, int fim, int l, int r) {
	if (l <= ini && fim <= r) return seg[pos];
	if (r < ini || fim < l) return node();

	int m = (ini + fim)/2;
	return query(2*pos, ini, m, l, r) + query(2*pos + 1, m + 1, fim, l, r);
}

void update(int pos, int ini, int fim, int idx, int x, bool b) {
	if (ini == fim) {
		if (b) { seg[pos].mx = x; seg[pos].sum = x; }
		else if (seg[pos].mx > 0) { seg[pos].mx += x; seg[pos].sum += x; }
		return;
	}

	int m = (ini + fim)/2;
	if (idx <= m) update(2*pos, ini, m, idx, x, b);
	else update(2*pos + 1, m + 1, fim, idx, x, b);

	seg[pos] = seg[2*pos] + seg[2*pos + 1];
}

void build(int pos, int ini, int fim) {
	if (ini == fim) {
		seg[pos] = node(xs[ini], ini, xs[ini]);
		return;
	}

	int m = (ini + fim)/2;
	build(2*pos, ini, m);
	build(2*pos + 1, m + 1, fim);

	seg[pos] = seg[2*pos] + seg[2*pos + 1];
}

void initialise(int sz, int q, int hs[]) {
	for (int i = 1; i <= sz; ++i)
		xs[i] = hs[i];

	build(1, 1, sz);
	n = sz;
}

void cut(int l, int r, int k) {
	for (int j = 0; j < k; ++j) {
		int i = query(1, 1, n, l, r).idx;
		update(1, 1, n, i, -1, false);
	}
}

void magic(int i, int x) {
	update(1, 1, n, i, x, true);
}

lli inspect(int l, int r) {
	return query(1, 1, n, l, r).sum;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19200 KB Output is correct
2 Correct 8 ms 19028 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19200 KB Output is correct
2 Correct 8 ms 19028 KB Output is correct
3 Correct 48 ms 20096 KB Output is correct
4 Correct 56 ms 20136 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 19028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 19028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 22888 KB Output is correct
2 Correct 122 ms 30160 KB Output is correct
3 Execution timed out 2071 ms 20892 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19200 KB Output is correct
2 Correct 8 ms 19028 KB Output is correct
3 Correct 48 ms 20096 KB Output is correct
4 Correct 56 ms 20136 KB Output is correct
5 Execution timed out 2070 ms 19028 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19200 KB Output is correct
2 Correct 8 ms 19028 KB Output is correct
3 Correct 48 ms 20096 KB Output is correct
4 Correct 56 ms 20136 KB Output is correct
5 Execution timed out 2070 ms 19028 KB Time limit exceeded
6 Halted 0 ms 0 KB -