제출 #1242325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242325		erray	나일강 (IOI24_nile)	C++20	13 / 100	52 ms	8636 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"

using namespace std;

#ifdef DEBUG 
	#include "debug.h"
#else 
	#define debug(...) void(37)	
#endif

template<typename T> void cmin(T& x, T y) { x = min(x, y); }

constexpr int MAX_W = int(1e9);

struct segment_info {
	int size;
	int best_active = MAX_W;
	array<int, 2> best_passive{MAX_W, MAX_W};
};

segment_info merge(segment_info l, segment_info r) {
	int parity = l.size % 2;
	cmin(l.best_active, r.best_active);
	cmin(l.best_passive[0], r.best_passive[parity]);
	cmin(l.best_passive[1], r.best_passive[!parity]);
	l.size += r.size;
	return l;
}

struct DSU {
	vector<int> link, right;
	vector<segment_info> info;
	
	DSU(vector<int> sizes) {
		int n = int(sizes.size());
		link.resize(n);
		iota(link.begin(), link.end(), 0);
		right = link;
		info.resize(n);
		for (int i = 0; i < n; ++i) info[i].size = sizes[i];
	}

	int get(int x) {
		return link[x] = (link[x] == x ? x : get(link[x]));
	}

	bool unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return false;
		if (x > y) swap(x, y);
		info[x] = merge(info[x], info[y]); 
		right[x] = y;
		link[y] = x;
		return true;
	}
	
	int cost(int v) {
		v = get(v);
		if (info[v].size % 2 == 0) return 0;
		return min(info[v].best_active, info[v].best_passive[0]);
	}
};

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
	int N = int(W.size());
	int Q = int(E.size());
	vector<int> coords = W;
	sort(coords.begin(), coords.end());
	coords.erase(unique(coords.begin(), coords.end()), coords.end());

	int s = int(coords.size());
	vector<int> min_d(s, MAX_W);
	vector<int> sizes(s);
	for (int i = 0; i < N; ++i) {
		int id = int(lower_bound(coords.begin(), coords.end(), W[i]) - coords.begin());
		min_d[id] = min(min_d[id], A[i] - B[i]);
		sizes[id]++;
	}
	DSU dsu(sizes);
	for (int i = 0; i < N; ++i) {
		if (sizes[i] == 1) {
			dsu.info[i].best_passive[0] = min_d[i];
		} else {
			dsu.info[i].best_active = min_d[i];
		}
	}

	vector<array<int, 2>> events;
	for (int i = 0; i < s - 1; ++i) {
		events.push_back({coords[i + 1] - coords[i], i});
	}
	for (int i = 1; i < s - 1; ++i) {
		events.push_back({coords[i + 1] - coords[i - 1], ~i});
	}
	sort(events.begin(), events.end());
	int64_t sum = accumulate(B.begin(), B.end(), int64_t(0));
	int64_t cur_ans = 0;
	for (int i = 0; i < s; ++i) cur_ans += dsu.cost(i);
	vector<int> q_ord(Q);
	iota(q_ord.begin(), q_ord.end(), 0);
	sort(q_ord.begin(), q_ord.end(), [&](int x, int y) {
		return E[x] < E[y];
	});
	vector<long long> ans(Q);
	int ans_p = 0;
	for (auto[t, e] : events) {
		while (ans_p < Q && E[q_ord[ans_p]] < t) {
			ans[q_ord[ans_p++]] = cur_ans + sum;
		}
		if (e < 0) {
			e = ~e;
			int l = dsu.get(e);
			cur_ans -= dsu.cost(l);
			cmin(dsu.info[l].best_active, min_d[e]);
			cur_ans += dsu.cost(l);
		} else {
			cur_ans -= dsu.cost(e) + dsu.cost(e + 1);
			dsu.unite(e, e + 1);
			cur_ans += dsu.cost(e);
		}
	}
	while (ans_p < Q) ans[q_ord[ans_p++]] = cur_ans + sum;
	return ans;
}

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