제출 #645932

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645932		TimDee	Weirdtree (RMI21_weirdtree)	C++17	0 / 100	2061 ms	32432 KiB

weirdtree

#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i=0; i<n; ++i)
using ll = long long;

struct RMQ {

	vector<ll>t,a;
	int size=1, n;

	int merge(int i, int j) {
		if (a[i]>=a[j]) return i;
		else return j;
	}

	void update(int i, int l, int r, int p) {
		if (r-l==1) return;
		if (r<=p || l>p) return;
		int mid=(r+l)>>1;
		update(2*i+1,l,mid,p);
		update(2*i+2,mid,r,p);
		t[i]=merge(t[2*i+1],t[2*i+2]);
	}

	void update(int i, int l, int r) {
		if (r-l==1) return;
		int mid=(r+l)>>1;
		update(2*i+1,l,mid);
		update(2*i+2,mid,r);
		t[i]=merge(t[2*i+1],t[2*i+2]);
	}

	RMQ(vector<ll>&v) {
		a=v;
		a.push_back(-1e9);
		n=a.size();
		while (size<n) size<<=1;
		t.assign(2*size-1,n);
		forn(i,n) t[size-1+i]=i;
		update(0,0,size);
	}

	int query(int i, int l, int r, int lx, int rx) {
		if (l>=rx || r<=lx) return n;
		if (l>=lx && r<=rx) return t[i];
		int mid=(l+r)>>1;
		int L=query(2*i+1,l,mid,lx,rx);
		int R=query(2*i+2,mid,r,lx,rx);
		return merge(L,R);
	}

	int query(int l, int r) {
		return query(0,0,size,l,r);
	}

	void set(int i, int x) {
		a[i]=x;
		update(0,0,size,i);
	}

};

struct aint {

	vector<ll>t,a;
	int size=1, n;

	ll merge(int i, int j) {
		return i+j;
	}

	void update(int i, int l, int r, int p) {
		if (r-l==1) return;
		if (r<=p || l>p) return;
		int mid=(r+l)>>1;
		update(2*i+1,l,mid,p);
		update(2*i+2,mid,r,p);
		t[i]=merge(t[2*i+1],t[2*i+2]);
	}

	void update(int i, int l, int r) {
		if (r-l==1) return;
		int mid=(r+l)>>1;
		update(2*i+1,l,mid);
		update(2*i+2,mid,r);
		t[i]=merge(t[2*i+1],t[2*i+2]);
	}

	aint(vector<ll>&v) {
		a=v;
		n=a.size();
		while (size<n) size<<=1;
		t.assign(2*size-1,0);
		forn(i,n) t[size-1+i]=a[i];
		update(0,0,size);
	}

	int query(int i, int l, int r, int lx, int rx) {
		if (l>=rx || r<=lx) return 0;
		if (l>=lx && r<=rx) return t[i];
		int mid=(l+r)>>1;
		int L=query(2*i+1,l,mid,lx,rx);
		int R=query(2*i+2,mid,r,lx,rx);
		return merge(L,R);
	}

	int query(int l, int r) {
		return query(0,0,size,l,r);
	}

	void set(int i, int x) {
		t[size-1+i]=x;
		update(0,0,size,i);
	}

};

vector<ll> a;
int n;
aint st(a);
RMQ rmq(a);

void initialise(int N, int Q, int*v) {
	n=N;
	forn(i,n) a.push_back(v[i+1]);
	st=aint(a);
	rmq=RMQ(a);
}

void cut(int l, int r, int k) {
	forn(q,k) {
		int i=rmq.query(l-1,r);
		if (!a[i]) break;
		a[i]--;
		rmq.set(i,a[i]);
		st.set(i,a[i]);
	}
}

void magic(int i, int x) {
	--i;
	a[i]=x;
	rmq.set(i,x);
	st.set(i,x);
}

ll inspect(int l, int r) {
	ll ans=st.query(l-1,r);
	return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 10
• Subtask 6: 0 / 21
• Subtask 7: 0 / 29