oj.uz

Submission #744088

# Submission time Handle Problem Language Result Execution time Memory
744088 2023-05-18T07:59:11 Z hmm789 Weirdtree (RMI21_weirdtree) C++14
13 / 100
 2000 ms 50648 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
struct node {
	int s, e, m, mx, midx, sm;
	node *l, *r;
	node(int _s, int _e) {
		s = _s, e = _e, m = (s+e)/2, mx = 0, midx = s, sm = 0;
		if(s != e) {
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void update(int x, int val) {
		if(s == e) {
			mx = sm = val;
			return;
		} else if(x > m) r->update(x, val);
		else l->update(x, val);
		sm = l->sm + r->sm;
		if(l->mx >= r->mx) {
			mx = l->mx;
			midx = l->midx;
		} else {
			mx = r->mx;
			midx = r->midx;
		}
	}
	pair<int, int> rmax(int x, int y) {
		if(x <= s && e <= y) return {mx, midx};
		else if(x > m) return r->rmax(x, y);
		else if(y <= m) return l->rmax(x, y);
		else {
			pair<int, int> tmp = l->rmax(x, y);
			pair<int, int> tmp2 = r->rmax(x, y);
			if(tmp.first >= tmp2.first) return tmp;
			else return tmp2;
		}
	}
	int rsum(int x, int y) {
		if(x <= s && e <= y) return sm;
		else if(x > m) return r->rsum(x, y);
		else if(y <= m) return l->rsum(x, y);
		else return l->rsum(x, y) + r->rsum(x, y);
	}
} *root;
#undef int

void initialise(int N, int Q, int h[]) {
	root = new node(0, N-1);
	for(int i = 0; i < N; i++) {
		root->update(i, h[i+1]);
	}
}
void cut(int l, int r, int k) {
	l--; r--;
	for(int i = 0; i < k; i++) {
		pair<int, int> tmp = root->rmax(l, r);
		if(tmp.first) root->update(tmp.second, tmp.first-1);
	}
}
void magic(int i, int x) {
	i--;
	root->update(i, x);
}
long long int inspect(int l, int r) {
	l--; r--;
	return root->rsum(l, r);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 79 ms 14400 KB Output is correct
4 Correct 81 ms 14116 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 468 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 2048 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 46872 KB Output is correct
2 Correct 189 ms 50648 KB Output is correct
3 Execution timed out 2061 ms 13824 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 79 ms 14400 KB Output is correct
4 Correct 81 ms 14116 KB Output is correct
5 Execution timed out 2048 ms 468 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 79 ms 14400 KB Output is correct
4 Correct 81 ms 14116 KB Output is correct
5 Execution timed out 2048 ms 468 KB Time limit exceeded
6 Halted 0 ms 0 KB -