제출 #1210629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210629		PenguinsAreCute	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	0 / 100	7 ms	1608 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(69);
struct node {
	node *l, *r;
	int key, val, sz;
	long long sum, pri;
	node(int x, int v): pri(rng()), key(x), val(v), sz(1), sum(v), l(NULL), r(NULL) {}
};
long long sum(node *x) {return x?x->sum:0;}
int sz(node *x) {return x?x->sz:0;}
void comp(node *x) {
	x->sum = sum(x->l) + sum(x->r) + x->val;
	x->sz = sz(x->l) + sz(x->r) + 1;
}
void split(int pt, node *x, node *&l, node *&r) {
	if(!x) {
		l=r=NULL;
		return;
	}
	if((x->key) < pt) {
		split(pt,x->r,x->r,r);
		comp(x);
		l=x;
	} else {
		split(pt,x->l,l,x->l);
		comp(x);
		r=x;
	}
}
void merge(node *&x, node *l, node *r) {
	if(!l||!r)
		x = (l?l:r);
	else if(l->pri > r->pri) {
		merge(l->r,l->r,r);
		x = l;
	} else {
		merge(r->l,l,r->l);
		x = r;
	}
	comp(x);
}
int bsta(long long s, node *x) {	
	if(!x)
		return (s<0?-1:1e9);
	if(sum(x->l)>s)
		return bsta(s, x->l);
	if(sum(x->l) + x->val > s)
		return x->key;
	return  bsta(s-sum(x->l)-x->val,x->r);
}
template<typename F>
void proc(node *x, F f) {
	if(!x)
		return;
	proc(x->l,f);
	f(x);
	proc(x->r,f);
}
signed main() {
	int n;
	cin >> n;
	int a[n], h[n], c[n];
	for(int i=0;i<n;i++) {
		cin >> a[i] >> h[i] >> c[i];
		a[i]--;
	}
	node* delta[n];
	for(int i=0;i<n;i++)
		delta[i] = NULL;
	for(int i=n;i--;) {
		if(0) proc(delta[i],[&i](node *k) {
			printf("node%ds +%d @%d\n", i, k->val, k->key);
		});
		node *l, *r;
		split(h[i], delta[i], l, r);
		merge(r, new node(h[i], c[i]), r);
		int pt = bsta(sum(l) - c[i], l);
		node *ll, *lr;
		split(pt, l, ll, lr);
		if(sum(lr) > c[i])
			merge(ll, ll, new node(pt, sum(lr) - c[i]));
		merge(delta[i], ll, r);
		if(0) proc(delta[i],[&i](node *k) {
			printf("node%dt +%d @%d\n", i, k->val, k->key);
		});
		if(!i)
			break;
		if(sz(delta[i]) > sz(delta[a[i]]))
			swap(delta[i], delta[a[i]]);
		node *&par = delta[a[i]];
		auto ins = [&par](node *k) {
			node *l, *r;
			split(k->key, par, l, r);
			merge(par, l, new node(k->key, k->val));
			merge(par, par, r);
		};
		proc(delta[i], ins);
	}
	long long ans = -delta[0]->sum;
	for(int i=0;i<n;i++)
		ans += c[i];
	cout << ans;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21