Submission #744030

#	Time	Username	Problem	Language	Result	Execution time	Memory
744030		salmon	Weirdtree (RMI21_weirdtree)	C++14	13 / 100	156 ms	41604 KiB

weirdtree

#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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 10
• Subtask 6: 0 / 21
• Subtask 7: 0 / 29