Submission #598636

#	Time	Username	Problem	Language	Result	Execution time	Memory
598636		CaroLinda	Weirdtree (RMI21_weirdtree)	C++14	13 / 100	2071 ms	6104 KiB

weirdtree

#include "weirdtree.h"
#include <bits/stdc++.h>

//solving for k == 1

#define ll long long

const int MAXN = 8e4+10;

using namespace std;

int N, Q;
int mx[MAXN*4];
ll soma[MAXN*4];

int m(int l, int r){
	return (l+r)>>1;
}

void updPoint(int pos, int l, int r, int id, int val){
	if(l == r){
		mx[pos] = val;
		soma[pos] = val;
		return;
	}

	if(id <= m(l,r))
		updPoint(pos<<1, l, m(l,r), id, val);
	else updPoint(pos<<1|1, m(l,r)+1, r, id, val);

	soma[pos] = soma[pos<<1]+soma[pos<<1|1];
	mx[pos] = max(mx[pos<<1],mx[pos<<1|1]);
}

ll qry(int pos, int l, int r, int beg, int en){
	if( l > en || r < beg)
		return 0LL;

	if(l >= beg && r <= en)
		return soma[pos];

	ll al = qry(pos<<1 , l , m(l,r), beg, en);
	ll ar = qry(pos<<1|1,m(l,r)+1, r, beg, en);

	return al+ar;
}

vector<tuple<int,int,int> > q;

void findVector(int pos, int l, int r, int beg, int en){
	if(l > en || r < beg)
		return ;

	if(l >= beg && r <= en)
		return (void)(q.push_back(make_tuple(pos,l,r)));

	findVector(pos<<1 , l, m(l,r), beg, en);
	findVector(pos<<1|1, m(l,r)+1, r, beg, en);
}

void updateInside(int pos, int l, int r){
	soma[pos]--;
	if(l == r){
		mx[pos]--;
		return;
	}

	if(mx[pos] == mx[pos<<1])
		updateInside(pos<<1 , l ,m(l,r));
	else updateInside(pos<<1|1 , m(l,r)+1, r);

	mx[pos] = max(mx[pos<<1], mx[pos<<1|1]);
}

void updateBig(int pos, int l, int r, int beg, int en){
	if(l == beg && r == en)
		return;

	if(en <= m(l,r))
		updateBig(pos<<1 , l , m(l,r), beg, en );
	else updateBig(pos<<1|1,m(l,r)+1, r, beg, en);

	soma[pos] = soma[pos<<1]+soma[pos<<1|1];
	mx[pos] = max(mx[pos<<1], mx[pos<<1|1]);
}

void callUpdateMax(int beg, int en){
	q.clear();
	findVector(1,1,N,beg,en);

	int curMax = 0, pos = -1, l, r;

	for(auto &e: q){
		if(mx[get<0>(e)] > curMax){
			curMax = mx[get<0>(e)];
			pos = get<0>(e);
			l = get<1>(e);
			r = get<2>(e);
		}
	}

	//there is nothing to do
	if(pos == -1)
		return;

	//go to max
	updateInside(pos, l,r);
	updateBig(1,1,N, l, r);
}


void initialise(int n, int q, int h[]) {
	N = n;
	Q = q;

	for(int i = 1; i <= N; i++)
		updPoint(1,1,N, i, h[i]);
}
void cut(int l, int r, int k) {
	while(k--){
		callUpdateMax(l,r);
	}
}
void magic(int i, int x) {
	updPoint(1,1,N, i, x);
}
long long int inspect(int l, int r) {
	return qry(1,1,N, 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