Submission #1210745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210745		PenguinsAreCute	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	484 ms	117676 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], d[n];
	memset(d,0,sizeof(d));
	for(int i=0;i<n;i++) {
		cin >> a[i] >> h[i] >> c[i];
		d[--a[i]]++;
	}
	node* delta[n];
	for(int i=0;i<n;i++)
		delta[i] = NULL;
	auto dip = [](node *&x, int hv, int cv) {
		node *l, *r;
		split(hv, x, l, r);
		merge(r, new node(hv, cv), r);
		int pt = bsta(sum(l) - cv, l);
		node *ll, *lr;
		split(pt, l, ll, lr);
		if(sum(lr) > cv)
			merge(ll, ll, new node(pt, sum(lr) - cv));
		merge(x, ll, r);
	};
	auto add = [](node *&x, node *&y) {
		if(sz(x) > sz(y))
			swap(x, y);
		auto ins = [&y](node *k) {
			node *l, *r;
			split(k->key, y, l, r);
			merge(y, l, new node(k->key, k->val));
			merge(y, y, r);
		};
		proc(x, ins);
	};
	for(int j=0;j<n;j++)
		for(int i=j;!d[i];i=a[i]) {
			d[i]--;
			d[a[i]]--;
			dip(delta[i], h[i], c[i]);
			add(delta[i], delta[a[i]]);
		}
	long long ans = 0;
	for(int i=0;i<n;i++)
		ans += c[i];
	for(int i=0;i<n;i++)
		if(d[i]>0) {
			vector<int> v = {i};
			int j = i;
			int cnt = 0;
			do {
				if(a[j] != j) {
					add(delta[j], delta[a[j]]);
					delta[j] = NULL;
				}
				d[j] = 0;
				j = a[j];
			} while(j != i);
			vector<pair<int,long long>> op;
			proc(delta[i], [&op](node *k) {op.push_back({k->key,(k->val)});});
			do {
				op.push_back({h[j],c[j]});
				op.push_back({h[j]-1,-c[j]});
				j = a[j];
			} while(j != i);
			sort(op.begin(),op.end(),greater<pair<int,long long>>());
			long long best = sum(delta[i]);
			long long cur = 0;
			for(auto [x, y]: op) {
				cur += y;
				best = max(best, cur);
			}
			ans -= best;
		}
	cout << ans;
}

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