Submission #1150949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150949		ZloyHR	나일강 (IOI24_nile)	C++20	38 / 100	69 ms	10940 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;
	V<ll> sum, oddMn, evenMn, minW;
	ll ans = 0;
	explicit DSU(const int n, V<int> &a, V<int> &b): parent_size(n, -1), sum(n, 0), a(a), b(b), oddMn(n), evenMn(n), minW(n) {
		FOR(i, 0, n) {
			minW[i] = weight[i];
			oddMn[i] = a[i] - b[i], evenMn[i] = LLONG_MAX >> 4;
			sum[i] = b[i];
			ans += a[i];
		}
	}

	ll calcAns(int idx) {
		if (-parent_size[idx] % 2 == 0) return sum[idx];
		else return sum[idx] + min(evenMn[idx], oddMn[idx]);
	}

	void update(int idx, ll val) {
		idx = leader(idx);
		ans -= calcAns(idx);
		chmin(oddMn[idx], val);
		chmin(evenMn[idx], val);
		ans += calcAns(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 -= calcAns(y);

		if (minW[y] < minW[x]) swap(x, y);
		chmin(oddMn[x], (-parent_size[x] % 2 == 0) ? oddMn[y] : evenMn[y]);
		chmin(evenMn[x], (-parent_size[x] % 2 == 0) ? evenMn[y] : oddMn[y]);
		if(-parent_size[x] < -parent_size[y]) swap(x, y);

		sum[x] += sum[y];
		parent_size[x] += parent_size[y];
		parent_size[y] = x;

		ans += calcAns(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]; });
	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]]); });

	FOR(i, 0, W.size()) weight[i] = W[i];
	priority_queue<pii, V<pii>, greater<>> pq;
	FOR(i, 1, W.size() - 1) {
		pq.emplace(W[ordWeights[i + 1]] - W[ordWeights[i - 1]], i);
	}

	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;
		}
		while (!pq.empty()) {
			auto [val, ordI] = pq.top();
			if (val > E[idx]) break;
			dsu.update(ordI, A[ordI] - B[ordI]);
			pq.pop();
		}
		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: 6 / 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