Submission #391302

#	Time	Username	Problem	Language	Result	Execution time	Memory
391302		Mlxa	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	79 / 100	1766 ms	403268 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define x first
#define y second
#define mp make_pair
#define mt make_tuple
#define all(x) x.begin(), x.end()

const int NODES = 4e6 + 10;
mt19937 rnd;

struct node {
	int x, w, dy, sy, ls, rs;
} pool[NODES];
int ff = 1;

#define getter(f) int &f(int v) { assert(0 <= v && v < NODES); return pool[v].f; }
getter(x) getter(w) getter(dy) getter(sy) getter(ls) getter(rs)

int new_node(int nx, int ny) {
	assert(ff < NODES);
	int v = ff++;
	x(v) = nx;
	w(v) = (int)rnd();
	dy(v) = ny;
	sy(v) = ny;
	ls(v) = rs(v) = 0;
	return v;
}

int pull(int v) {
	sy(v) = sy(ls(v)) + dy(v) + sy(rs(v));
	return v;
}

void to_vector(int t, vector<pair<int, int>> &vec) {
	if (!t) {
		return;
	}
	to_vector(ls(t), vec);
	vec.emplace_back(x(t), dy(t));
	to_vector(rs(t), vec);
}

void print(int t) {
	vector<pair<int, int>> v;
	to_vector(t, v);
	for (auto e : v) {
		cout << "(" << e.x << "; " << e.y << ") ";
	}
	cout << endl;
}


pair<int, int> splitsum(int t, int s) {
	if (!t) {
		return {0, 0};
	}
	// print(t);
	assert(0 <= s && s <= sy(t));
	int lsum = sy(ls(t)), msum = dy(t);
	if (lsum < s && lsum + msum > s) {
		int lt = new_node(x(t), s - lsum), rt = new_node(x(t), msum - dy(lt));
		ls(lt) = ls(t), rs(rt) = rs(t);
		return {pull(lt), pull(rt)};
	}
	int l, r;
	if (s <= lsum) {
		tie(l, ls(t)) = splitsum(ls(t), s);
		r = pull(t);
	} else {
		tie(rs(t), r) = splitsum(rs(t), s - lsum - msum);
		l = pull(t);
	}
	assert(sy(l) == s);
	return {l, r};
}

// (-inf, k], (k, +inf)
pair<int, int> split(int t, int k) {
	if (!t) {
		return {0, 0};
	}
	int l, r;
	if (k < x(t)) {
		tie(l, ls(t)) = split(ls(t), k);
		r = pull(t);
	} else {
		tie(rs(t), r) = split(rs(t), k);
		l = pull(t);
	}
	return {l, r};
}

int merge(int l, int r) {
	if (!l) {
		return r;
	}
	if (!r) {
		return l;
	}
	if (w(l) < w(r)) {
		rs(l) = merge(rs(l), r);
		return pull(l);
	} else {
		ls(r) = merge(l, ls(r));
		return pull(r);
	}
}

int get_value(int t, int x) {
	int l, r;
	tie(l, r) = split(t, x);
	int res = sy(l);
	t = merge(l, r);
	return res;
}

__attribute__((warn_unused_result))
int insert(int t, int nx, int ny) {
	int l, m, r;
	tie(l, m) = split(t, nx - 1);
	tie(m, r) = split(m, nx);
	// cout << "insert " << nx << " " << ny << endl;
	// print(l);
	// print(m);
	// print(r);
	// cout << "---" << endl;
	m = new_node(nx, sy(m) + ny);
	l = merge(l, m);
	// print(l);
	return merge(l, r);
}

__attribute__((warn_unused_result))
int uminpref(int t, int px) {
	int checksum = sy(t);

	int l, m, r;
	tie(l, m) = split(t, px - 1);
	tie(m, r) = split(m, px);
	if (sy(m) <= 0) {
		int p, q;
		tie(p, q) = splitsum(l, sy(l) + sy(m));
		t = merge(p, r);
		assert(sy(t) == checksum);
		return t;
	} else {
		return merge(merge(l, m), r);
	}
}

__attribute__((warn_unused_result))
int add(int tv, int tu) {
	if (!tv) {
		return tu;
	}
	if (!tu) {
		return tv;
	}
	tv = insert(tv, x(tu), dy(tu));
	tv = add(tv, ls(tu));
	tv = add(tv, rs(tu));
	return tv;
}



const int N = 2e5 + 10;
int n, ia[N], ih[N], ic[N], dp[N];
vector<int> g[N];

bool used[N];

void dfs(int v) {
	used[v] = true;
	for (int u : g[v]) {
		if (used[u]) {
			continue;
		}
		dfs(u);
		dp[u] = uminpref(dp[u], ih[u]);
		// cout << "v = " << u + 1 << endl;
		// print(dp[u]);
		dp[v] = add(dp[v], dp[u]);
	}
	dp[v] = insert(dp[v], 0, ic[v]);
	dp[v] = insert(dp[v], ih[v], -ic[v]);
	dp[v] = insert(dp[v], ih[v] + 1, ic[v]);
}


signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0); cin.tie(0); 

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> ia[i] >> ih[i] >> ic[i];
		--ia[i];
		g[ia[i]].push_back(i);
	}
	int answer = 0;
	for (int i = 0; i < n; ++i) {
		if (used[i]) {
			continue;
		}
		int v = ia[i], u = ia[ia[i]];
		while (v != u) {
			v = ia[v];
			u = ia[ia[u]];
		}
		dfs(v);
		int t = dp[v];
		u = ia[u];
		// while (u != v) {
		// 	dfs(u);
		// 	t = add(t, dp[u]);
		// 	u = ia[u];
		// }
		// cout << "v = " << v + 1 << endl;
		// print(t);
		t = uminpref(t, ih[v]);
		t = insert(t, 0, 0);
		vector<pair<int, int>> ve;
		to_vector(t, ve);
		int cur = (int)1e18, y = 0;
		for (auto e : ve) {
			y += e.y;
			cur = min(cur, y);
		}
		answer += cur;
	}
	cout << answer << "\n";
	return 0;
}

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