Submission #1213688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213688		MuhammadSaram	Weirdtree (RMI21_weirdtree)	C++20	13 / 100	38 ms	3908 KiB

weirdtree

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

using namespace std;

#define ll long long

const int M = 80000 + 1;

struct node
{
	int mx=-1,id;
	ll su=0;
};

node seg[M*2];
int n;

node merge(node a,node b)
{
	a.su=b.su=a.su+b.su;
	if (a.mx<b.mx)
		return b;
	return a;
}

void modify(int p,int x,int v=0,int s=1,int e=n+1)
{
	if (s+1==e)
	{
		seg[v].mx=seg[v].su=x,seg[v].id=p;
		return;
	}
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	if (p<mid)
		modify(p,x,lc,s,mid);
	else
		modify(p,x,rc,mid,e);
	seg[v]=merge(seg[lc],seg[rc]);
}

node get(int l,int r,int v=0,int s=1,int e=n+1)
{
	if (l>=e or r<=s)
		return seg[M*2-1];
	if (l<=s && e<=r)
		return seg[v];
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	return merge(get(l,r,lc,s,mid),get(l,r,rc,mid,e));
}

void initialise(int N, int Q, int h[])
{
	n=N;
	for (int i=1;i<=n;i++)
		modify(i,h[i]);		
}
void cut(int l, int r, int k)
{
	node a=get(l,r+1);
	modify(a.id,a.mx-1);
}
void magic(int i, int x) {
	modify(i,x);
}
long long int inspect(int l, int r) {
	return get(l,r+1).su;
}

• 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