Submission #1240386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240386		hengliao	Tree (IOI24_tree)	C++20	100 / 100	196 ms	89032 KiB

tree

#include "tree.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef long long ll;

namespace{
	const ll mxN=2e5+5;
	const ll inf=1e18;
	const ll mxM=1e6+5;

	struct segtreeadd{
		vll tree;
		ll siz;

		void init(ll sz){
			siz=sz+1;
			tree=vll(siz, 0);
		}

		void update(ll idx, ll val){
			idx++;
			for(;idx<siz;idx+=(idx&(-idx))){
				tree[idx]+=val;
			}
		}

		ll getpre(ll idx){
			idx++;
			ll re=0;
			for(;idx>0;idx-=(idx&(-idx))){
				re+=tree[idx];
			}
			return re;
		}

		ll getsum(ll qlow, ll qhigh){
			return getpre(qhigh)-getpre(qlow-1);
		}
	};

	struct segtreemin{
		vector<pll> tree;
		ll treelen;

		void init(ll sz){
			treelen=sz+1;
			while(__builtin_popcount(treelen)!=1) treelen++;
			tree=vector<pll>(2*treelen, {inf, inf});
		}

		void update(ll idx, pll val){
			ll tar=idx+treelen;
			tree[tar]=val;
			tar/=2;
			while(tar>0){
				tree[tar]=min(tree[2*tar], tree[2*tar+1]);
				tar/=2;
			}
		}

		pll getmin1(ll idx, ll low, ll high, ll qlow, ll qhigh){
			if(low>=qlow && high<=qhigh){
				return tree[idx];
			}
			if(low>qhigh || high<qlow){
				return {inf, inf};
			}
			ll mid=(low+high)/2;
			return min(getmin1(2*idx, low, mid, qlow, qhigh),
				getmin1(2*idx+1, mid+1, high, qlow, qhigh));
		}

		pll getmin(ll qlow, ll qhigh){
			return getmin1(1, 0, treelen-1, qlow, qhigh);
		}
	};

	segtreeadd seg1;
	segtreemin seg2;

	ll n, l, r;
	ll p[mxN];
	ll w[mxN];
	vll adj[mxN];
	ll in[mxN], out[mxN];
	ll timer;
	ll ans;
	vector<array<ll, 5>> eq;
	ll leafsum;
	ll prel[mxM], prer[mxM];

	void dfs(ll cur){
		in[cur]=timer;
		out[cur]=timer;
		timer++;
		for(auto &chd:adj[cur]){
			dfs(chd);
			out[cur]=out[chd];
		}
	}

	void chainupd(ll t, ll b, ll val){
		seg1.update(in[b], val);
		if(p[t]!=-1){
			seg1.update(in[p[t]], -val);
		}
	}

	void f(ll cur){
		pll tep=seg2.getmin(in[cur], out[cur]);
		if(tep.F==inf) return;
		ll tar=tep.S;
		// cout<<seg1.getsum(in[cur], out[cur])<<'\n';
		ll total=seg1.getsum(in[cur], out[cur]);
		// ll mx=seg1.getsum(in[cur], out[cur])*l-r;
		// ll lef=0;
		// ll org=seg1.getsum(in[tar], out[tar])*l;
		ll th=seg1.getsum(in[tar], out[tar]);
		eq.pb({total-th+1, 0, -w[tar], 0, tar});
		eq.pb({total, total-th+1, (total-th)*w[tar], -w[tar], tar});
		// ll mntar=max(org-mx, l);
		for(auto &chd:adj[tar]){
			ll k=seg1.getsum(in[chd], out[chd]);
			// ll val=min(seg1.getsum(in[chd], out[chd])*l, r);
			// lef+=val;
			eq.pb({total, k, k*w[tar], 0, tar});
			eq.pb({k, 0, 0, w[tar], tar});
		}
		// ll minu=lef-mntar;
		// if(mx>0) ans+=w[tar]*minu;
		// cout<<"node: "<<tar<<' '<<lef<<' '<<mx<<'\n';
		chainupd(cur, tar, -(th-1));
		// cout<<"updating "<<cur<<' '<<tar<<' '<<-lef<<'\n';
		seg2.update(in[tar], {inf, inf});
		for(auto &chd:adj[tar]){
			f(chd);
		}
		f(cur);
	}
}

void init(vector<int> P, vector<int> W) {
	n=P.size();
	for(ll i=0;i<n;i++){
		p[i]=P[i];
		w[i]=W[i];
		if(i>0){
			adj[p[i]].pb(i);
		}
	}
	timer=0;
	dfs(0);
	leafsum=0;

	seg1.init(n);
	seg2.init(n);
	for(ll i=0;i<n;i++){
		if(in[i]==out[i]){
			seg1.update(in[i], 1);
			seg2.update(in[i], {inf, inf});
			leafsum+=w[i];
		}
		else{
			seg2.update(in[i], {w[i], i});
		}
	}
	f(0);

	for(auto &it:eq){
		prel[it[1]]+=it[2];
		prel[it[0]]-=it[2];
		prer[it[1]]+=it[3];
		prer[it[0]]-=it[3];
	}

	for(ll i=1;i<mxM;i++){
		prel[i]+=prel[i-1];
		prer[i]+=prer[i-1];
	}
}

long long query(int L, int R) {
	ans=0;
	l=L;
	r=R;
	ans+=leafsum*l;
	ll divi=r/l;

	ans+=prel[divi]*l+prer[divi]*r;
	
	return ans;
}	

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 18 / 18
• Subtask 4: 7 / 7
• Subtask 5: 11 / 11
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19