oj.uz

Submission #744030

# Submission time Handle Problem Language Result Execution time Memory
744030 2023-05-18T07:23:04 Z salmon Weirdtree (RMI21_weirdtree) C++14
13 / 100
 156 ms 41604 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> lst;

struct node{
	
	node *l,*r;
	int s,e,m;
	long long int v;
	pair<int,int> small;
	
	node(int S,int E){
		s = S;
		e = E;
		m = (s + e)/2;
		
		if(s == e){
			v = lst[s];
			small = make_pair(lst[s],-s); 
		}
		else{
			l = new node(s,m);
			r = new node(m + 1, e);
			
			small = max(l -> small, r -> small);
			v = l -> v + (long long int) r -> v; 
		}
	}
	
	long long int query(int S, int E){
		if(S <= s && e <= E){
			return v;
		}
		
		long long int V = 0;
		
		if(S <= m){
			V += l -> query(S,E);
		}
		if(m < E){
			V += r -> query(S,E);
		}
		
		return V;
	}
	
	pair<int,int> rmin(int S, int E){
		if(S <= s && e <= E){
			return small;
		}
		
		pair<int,int> V = make_pair(-1,0);
		
		if(S <= m) V = max(V,l -> rmin(S,E));
		if(m < E) V = max(V,r -> rmin(S,E));
		
		return V;
	}
	
	void update(int i, int k){
		if(s == e){
			v = k;
			small = make_pair(k,-s);
			return;
		}
		
		
		if(i <= m) l -> update(i,k);
		else r -> update(i,k);
			
		small = max(l -> small, r -> small);
		v = l -> v + (long long int) r -> v; 
		
	
	}
}*root;

void initialise(int N, int Q, int h[]) {
	lst.push_back(0);
	for(int i = 1; i <= N; i++){
		lst.push_back(h[i]);
	}
	
	root = new node(1,N);
}

void cut(int l, int r, int k) {
	pair<int,int> ii = root -> rmin(l,r);
	
	if(ii.first == 0){
		return;
	}
	
	root -> update(-ii.second,ii.first - 1);
}
void magic(int i, int x) {
	root -> update(i,x);
}
long long int inspect(int l, int r) {
	return root -> query(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 75 ms 10968 KB Output is correct
4 Correct 85 ms 10948 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 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 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 39188 KB Output is correct
2 Correct 156 ms 41604 KB Output is correct
3 Incorrect 23 ms 12364 KB Output isn't correct
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 75 ms 10968 KB Output is correct
4 Correct 85 ms 10948 KB Output is correct
5 Incorrect 1 ms 468 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 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 75 ms 10968 KB Output is correct
4 Correct 85 ms 10948 KB Output is correct
5 Incorrect 1 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -