Submission #1210630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210630		PenguinsAreCute	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	488 ms	112484 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(69);
struct node {
	node *l, *r;
	int key, sz;
	long long sum, val, pri;
	node(int x, long long 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;
	/*
	for(int i=n;--i;)
		sub[a[i]] += sub[i];
	hp[0]=0;
	for(int i=0;i<n;i++)
		if(adj[i].size()) {
			pair<int,int> bst = {-1,-1};
			for(auto j: adj[i])
				bst=max(bst,{sub[j],hp[j]=j});
			hp[bst.second] = hp[i];
		}
	*/
}

Compilation message (stderr)

worst_reporter2.cpp: In lambda function:
worst_reporter2.cpp:73:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   73 |                         printf("node%ds +%d @%d\n", i, k->val, k->key);
      |                                          ~^            ~~~~~~
      |                                           |               |
      |                                           int             long long int
      |                                          %lld
worst_reporter2.cpp: In lambda function:
worst_reporter2.cpp:85:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   85 |                         printf("node%dt +%d @%d\n", i, k->val, k->key);
      |                                          ~^            ~~~~~~
      |                                           |               |
      |                                           int             long long int
      |                                          %lld

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