Submission #1150865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150865		ZloyHR	Nile (IOI24_nile)	C++20	32 / 100	181 ms	57768 KiB

nile

#include "nile.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, pll> ppll;
typedef long double ld;
typedef tree<int,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define V vector
#define fst first
#define snd second
#define ins insert
#define pb push_back
#define eb emplace_back
#define dbgs(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)

template<typename T> void re(T &x) { cin >> x; }
template<typename T, typename ... U> void re(T &t, U &...u) { re(t); re(u...); }
template<typename T> void re(V<T> &x) { for(auto &a : x) re(a); }

template <typename T, typename V> ostream& operator<<(ostream& out, const pair<T, V> x) { out << "{" << x.fst << " : " << x.snd << "}"; return out; }
template <typename T> ostream& operator<<(ostream& out, const set<T> x) { for (auto& it : x) { out << it << " "; } return out; }
template <typename T> ostream& operator<<(ostream& out, const multiset<T> x) { for (auto& it : x) { out << it << " "; } return out; }
template <typename T, typename V> ostream& operator<<(ostream& out, const map<T, V> x) { for (auto& it : x) { out << "[" << it.fst << "]" << " = " << it.snd << "\n"; } return out; }
template <typename T> ostream& operator<<(ostream& out, const V<T> x) { if(!x.empty()) { for (int i = 0; i < x.size() - 1; ++i) { out << x[i] << " "; } out << x.back(); } return out; }
template <typename T> ostream& operator<<(ostream& out, const V<V<T>> x) { for (int i = 0; i < x.size() - 1; ++i) { out << "[" << i << "]" << " = {" << x[i] << "}\n"; } out << "[" << x.size() - 1 << "]" << " = {" << x.back() << "}\n"; return out; }
ostream& operator<<(ostream& out, const ordered_set x) { for (auto& it : x) { out << it << " "; } return out; }

template <class T, class U> inline void chmin(T& a, U&& b) { if (b < a) { a = b; } }
template <class T, class U> inline void chmax(T& a, U&& b) { if (a < b) { a = b; } }
template <class T, class U, class V> inline void clip(T& v, U&& lower, V&& upper) { if (v < lower) { v = lower; } else if (v > upper) { v = upper; } }

random_device dev;
mt19937 rng(dev());
//uniform_int_distribution<ll> dist(1,10);

const int N = 1e5 + 5;
int diff[N];
int weight[N];
struct DSU {
	V<int> parent_size, a, b, mn, mx, mx1, mx2;
	V<ll> sum;
	V<set<pll>> wh;
	ll ans = 0;
	explicit DSU(const int n, V<int> &a, V<int> &b): parent_size(n, -1), sum(n, 0), mx1(n), mx2(n), wh(n), a(a), b(b), mn(n), mx(n) {
		FOR(i, 0, n) {
			mn[i] = mx[i] = i;
			mx1[i] = a[i] - b[i];
			mx2[i] = INT_MAX;
			wh[i].emplace(diff[i], i);
			sum[i] = b[i];
			ans += a[i];
		}
	}

	int calcAns(int idx) {
		if (-parent_size[idx] % 2 == 0) return 0;
		if (-parent_size[idx] % 4 == 1) return mx1[idx];
		return min(mx2[idx], min(a[mn[idx]] - b[mn[idx]], a[mx[idx]] - b[mx[idx]]));
	}

	int merge(int x, int y, int d) {
		x = leader(x), y = leader(y);
		if(-parent_size[x] < -parent_size[y]) swap(x, y);
		ans -= calcAns(x);
		ans -= sum[x];
		ans -= calcAns(y);
		ans -= sum[y];
		sum[x] += sum[y];
		parent_size[x] += parent_size[y];
		parent_size[y] = x;
		for (auto &it : wh[y]) wh[x].ins(it);
		while (!wh[x].empty()) {
			auto it = wh[x].begin();
			if (it->fst > d) break;
			chmin(mx2[x], a[it->snd] - b[it->snd]);
			wh[x].erase(it);
		}
		chmin(mx1[x], mx1[y]);
		if (weight[mn[x]] < weight[mn[y]]) mn[x] = mn[y]; else mx[x] = mx[y];
		ans += calcAns(x);
		ans += sum[x];
		return x;
	}
	int leader(const int x) {
		if(parent_size[x] < 0) return x;
		return parent_size[x] = leader(parent_size[x]);
	}
	int size(const int x) {
		return -parent_size[leader(x)];
	}
	bool isSame(const int x, const int y) {
		return leader(x) == leader(y);
	}
};

// Nile
V<ll> calculate_costs(V<int> W, V<int> A, V<int> B, V<int> E) {
	V<int> ordQuery(E.size()); iota(all(ordQuery), 0);
	sort(all(ordQuery), [&](int i, int j) { return E[i] < E[j]; });
	V<int> ordWeights(W.size()); iota(all(ordWeights), 0);
	sort(all(ordWeights), [&](int i, int j) { return W[i] < W[j]; });
	FOR(i, 1, W.size() - 1) {
		diff[i] = W[ordWeights[i + 1]] - W[ordWeights[i - 1]];
	}
	V<int> ordWeightPairs(W.size() - 1); iota(all(ordWeightPairs), 0);
	sort(all(ordWeightPairs), [&](int i, int j) { return (W[ordWeights[i + 1]] - W[ordWeights[i]]) < (W[ordWeights[j + 1]] - W[ordWeights[j]]); });
	DSU dsu(W.size(), A, B);
	int i = 0;
	V<ll> ans(E.size());
	for (auto &idx : ordQuery) {
		while (i < ordWeightPairs.size()) {
			int ordI = ordWeightPairs[i];
			if (W[ordWeights[ordI + 1]] - W[ordWeights[ordI]] <= E[idx]) {
				dsu.merge(ordWeights[ordI + 1], ordWeights[ordI], E[idx]);
				++i;
			} else break;
		}
		ans[idx] = dsu.ans;
	}
	return ans;
}

// int main() {
// 	int N;
// 	assert(1 == scanf("%d", &N));
// 	std::vector<int> W(N), A(N), B(N);
// 	for (int i = 0; i < N; i++)
// 		assert(3 == scanf("%d%d%d", &W[i], &A[i], &B[i]));
// 	int Q;
// 	assert(1 == scanf("%d", &Q));
// 	std::vector<int> E(Q);
// 	for (int j = 0; j < Q; j++)
// 		assert(1 == scanf("%d", &E[j]));
// 	fclose(stdin);
//
// 	std::vector<long long> R = calculate_costs(W, A, B, E);
//
// 	int S = (int)R.size();
// 	for (int j = 0; j < S; j++)
// 		printf("%lld\n", R[j]);
// 	fclose(stdout);
//
// 	return 0;
// }

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18