Submission #791265

#	Time	Username	Problem	Language	Result	Execution time	Memory
791265		hugo_pm	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	800 ms	228932 KiB

worst_reporter2

#include <bits/stdc++.h>
// Begin treap.h
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Croix {
	ll key, val;
	bool operator<(const Croix& oth) const {
		if (key != oth.key)
			return key < oth.key;
		return val < oth.val; // ├á v├®rifier + INF ou -INF dans merge ?
	}
	bool operator==(const Croix &oth) const {
		return (key == oth.key) && (val == oth.val);
	}
};

string to_string(Croix c) {
	return "(" + to_string(c.key) + ", " + to_string(c.val) + ")";
}

namespace treap {
	const ll INF = 3e18;
	mt19937 rng(42);
	int gen_prio() {
		return uniform_int_distribution<int>(1, 1e9)(rng);
	}
	struct node {
		Croix x;
		int priority, size = 1;
		ll to_prop = 0;
		node *left = nullptr, *right = nullptr, *parent = nullptr;
		void update() {
			size = 1;
			if (left) {
				left->parent = this;
				size += left->size;
			}
			if (right) {
				right->parent = this;
				size += right->size;
			}
		}
	};
	void push(node* root) {
		if (root == nullptr) return;
		root->x.val += root->to_prop;
		if (root->left) root->left->to_prop += root->to_prop;
		if (root->right) root->right->to_prop += root->to_prop;
		root->to_prop = 0;
	}
	const int MAX_N = 200*1000*18;
	node buffer[MAX_N];
	int buff = 0;
	node* singleton(Croix c, node* from) {
		assert(buff < MAX_N);
		node* ret = &buffer[buff]; ++buff;
		ret->x = c, ret->parent = from, ret->priority = gen_prio();
		return ret;
	}
	node* min_element(node* root) {
		push(root);
		if (root == nullptr || root->left == nullptr) {
			return root;
		}
		return min_element(root->left);
	}
	node* max_element(node* root) {
		push(root);
		if (root == nullptr || root->right == nullptr) {
			return root;
		}
		return max_element(root->right);
	}
	void clear(node* root) {
		return; // using buffer
		if (root != nullptr) {
			clear(root->left);
			clear(root->right);
			delete root;
			root = nullptr;
		}
	}
	struct iterator {
		using iterator_category = std::bidirectional_iterator_tag;
		using difference_type   = std::ptrdiff_t;
		using value_type        = const Croix;
		using pointer           = Croix*;
		using reference         = const Croix;

		iterator(node* ptr, bool end) : m_ptr(ptr), m_end(end) {}
		reference operator*() const { return m_ptr->x; }
		pointer operator->() { return &(m_ptr->x); }
		iterator& operator++();  
		iterator operator++(int) { iterator tmp = *this; ++(*this); return tmp; }
		iterator& operator--(); 
		iterator operator--(int) { iterator tmp = *this; --(*this); return tmp; }
		friend bool operator== (const iterator& a, const iterator& b) {
			return (a.m_ptr == b.m_ptr) && (a.m_end == b.m_end);
		};
		friend bool operator!= (const iterator& a, const iterator& b) {
			return (a.m_ptr != b.m_ptr) || (a.m_end != b.m_end);
		};  

		node* m_ptr;
		bool m_end;
	};
	iterator& iterator::operator++() {
		if (m_ptr == nullptr || m_end) return *this;
		if (m_ptr->right != nullptr) {
			m_ptr = min_element(m_ptr->right);
		} else {
			auto cur = m_ptr, parent = m_ptr->parent;
			while (parent != nullptr && cur == parent->right) {
				cur = parent;
				parent = parent->parent;
			}
			if (parent != nullptr)
				m_ptr = parent;
			else
				m_end = true;
		}
		return *this;
	}
	iterator& iterator::operator--() {
		if (m_ptr == nullptr) return *this;
		if (m_end) { m_end = false; return *this; }
		if (m_ptr->left != nullptr) {
			m_ptr = max_element(m_ptr->left);
		} else {
			auto parent = m_ptr->parent;
			while (parent != nullptr && m_ptr == parent->left) {
				m_ptr = parent;
				parent = parent->parent;
			}
			m_ptr = parent;
		}
		return *this;
	}

	pair<node*, node*> split(const Croix splitter, bool equalToLeft, node* root) {
		if (root == nullptr) {
			return {nullptr, nullptr};
		}
		root->parent = nullptr;
		push(root);
		bool curInLeft = (root->x < splitter || (root->x == splitter && equalToLeft));
		if (curInLeft) {
			auto [RL, RR] = split(splitter, equalToLeft, root->right);
			root->right = RL;
			root->update();
			return {root, RR};
		} else {
			auto [LL, LR] = split(splitter, equalToLeft, root->left);
			root->left = LR;
			root->update();
			return {LL, root};
		}
	}

	node* merge(node* L, node* R) {
		if (L == nullptr || R == nullptr) {
			return (L ? L : R);
		}
		node* root;
		if (L->priority > R->priority) {
			L->right = merge(L->right, R);
			root = L;
		} else {
			R->left = merge(L, R->left);
			root = R;
		}
		root->update();
		return root;
	}

	node* lower_bound(const Croix val, node* root) {
		if (root == nullptr) return nullptr;
		push(root);
		if (root->x < val) {
			return lower_bound(val, root->right);
		} else {
			node* ret = lower_bound(val, root->left);
			return (ret ? ret : root);
		}
	}

	void add(const ll until, const ll delta, node* root) {
		if (root == nullptr) return;
		push(root);
		if (root->x.key > until) {
			return add(until, delta, root->left);
		}
		if (root->left) {
			root->left->to_prop += delta;
		}
		root->x.val += delta;
		add(until, delta, root->right);
	}

	class tree {
		public:
		using iterator = treap::iterator;
		size_t size() { return (m_root ? m_root->size : 0); }
		bool empty() { return m_root == nullptr; }
		void swap(tree &oth) { std::swap(m_root, oth.m_root); }
		void clear() { treap::clear(m_root); }
		iterator begin() { return iterator(min_element(m_root), m_root == nullptr); }
		iterator end()   { return iterator(max_element(m_root), true); }
		pair<iterator, bool> insert(Croix x) {
			auto [L, R] = treap::split(x, false, m_root);
			node* M = singleton(x, nullptr);
			m_root = merge(merge(L, M), R);
			return {iterator(M, false), true};
		}
		void erase(Croix x) {
			auto [leftStrict, rightLarge] = treap::split(x, false, m_root);
			auto [toDel, rightStrict] = treap::split(x, true, rightLarge);
			treap::clear(toDel);
			m_root = merge(leftStrict, rightStrict);
		}
		void erase(iterator it) {
			erase(*it);
		}
		iterator lower_bound(Croix x) {
			node* ptr = treap::lower_bound(x, m_root);
			return (ptr ? iterator(ptr, false) : end());
		}
		void add(ll until, ll delta) {
			treap::add(until, delta, m_root);
		}
		private:
		node* m_root = nullptr;
	};
};
// End treap.h
#define int long long
using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define sz(v) ((int)((v).size()))

template<typename T>
void chmax(T &x, const T &v) { if (x < v) x = v; }
template<typename T>
void chmin(T &x, const T &v) { if (x > v) x = v; }

using pii = pair<int, int>;
using vi = vector<int>;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int INF = 3e18;
const int MAX_N = 2e5 + 5;
int nbNode;
treap::tree profile[MAX_N];
int costDel[MAX_N], hauteur[MAX_N];
vector<int> children[MAX_N];

void insere(treap::tree &dest, Croix c) {
	auto it = dest.lower_bound(c);
	if (it == dest.end() || c.val > it->val) {
		it = dest.insert(c).first;
		while (it != dest.begin() && prev(it)->val <= c.val) {
			dest.erase(prev(it));
			it = dest.lower_bound(c);
		}
	}
}
void merge(int iDest, int iSrc) {
	if (profile[iDest].size() < profile[iSrc].size()) {
		profile[iDest].swap(profile[iSrc]);
	}
	auto &dest = profile[iDest], &src = profile[iSrc];
	assert(!dest.empty());
	// Calcule les pts bleus
	vector<Croix> cand;
	for (Croix c : src) {
		auto it = dest.lower_bound({c.key, -INF});
		int nxRed = (it != dest.end() ? it->val : 0);
		cand.push_back({c.key, c.val + nxRed});
	}
	// Am├®liore les pts rouges
	int previously = 0;
	vector<Croix> revSrc(src.begin(), src.end());
	reverse(all(revSrc));
	for (Croix c : revSrc) {
		dest.add(c.key, c.val - previously);
		previously = c.val;
	}
	src.clear();
	// Insère les pts bleus
	for (Croix c : cand) {
		insere(dest, c);
	}
}

const int FAKE = MAX_N-1;
void dfs(int node) {
	int takeNode = costDel[node];
	for (int child : children[node]) {
		dfs(child);
		auto it = profile[child].lower_bound({hauteur[node], -INF});
		if (it != profile[child].end()) {
			takeNode += it->val;
		}
		merge(node, child);
	}
	insere(profile[node], {hauteur[node], takeNode});
	// dbg(node, vector<Croix>(all(profile[node])));
	// dbg(takeNode, dontTake);
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> nbNode;
	int totCost = 0;
	rep(i, 0, nbNode) {
		int p;
		cin >> p >> hauteur[i] >> costDel[i];
		totCost += costDel[i];
		if (i > 0) {
			children[p-1].push_back(i);
		}
	}
	dfs(0);
	cout << totCost - profile[0].begin()->val << '\n';
}

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