Submission #34118

#	Time	Username	Problem	Language	Result	Execution time	Memory
34118		natsukagami	도로 건설 사업 (JOI13_construction)	C++14	100 / 100	1539 ms	98124 KiB

construction

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> Edge;
const int maxn = 2e5 + 5;

int N, M, C;
ii P[maxn];
ii RA[maxn], RB[maxn];
int H[3 * maxn], B[3 * maxn];

Edge E[4 * maxn]; int ec = 0;

int X[3 * maxn];
int K;
int pos(int x) { return lower_bound(X + 1, X + K + 1, x) - X; }
vector<ii> Evt[3 * maxn];
vector<ii> Ask[3 * maxn];
void build_edges() {
	K = 2 * M + N;
	// Compress coordinates
	for (int i = 1; i <= N; ++i) X[i] = P[i].x;
	for (int i = 1; i <= M; ++i) X[i + N] = RA[i].x, X[i + N + M] = RB[i].x + 1;
	sort(X + 1, X + K + 1);
	// Add queries
	for (int i = 1; i <= N; ++i) {
		Ask[pos(P[i].x)].emplace_back(P[i].y, i);
	}
	// Add events
	for (int i = 1; i <= M; ++i) {
		Evt[pos(RA[i].x)].emplace_back(RA[i].y, i);
		Evt[pos(RB[i].x + 1)].emplace_back(RA[i].y, -i);
	}
	// Process 
	multiset<int> S;
	for (int i = 1; i <= K; ++i) {
		// add / remove rectangles
		for (auto &u: Evt[i]) {
			if (u.y > 0) S.insert(u.x);
			else S.erase(S.lower_bound(u.x));
		}
		// process edge queries
		sort(Ask[i].begin(), Ask[i].end());
		for (int j = 1; j < Ask[i].size(); ++j) {
			// check if there's a rect between Ask[i][j - 1] and Ask[i][j]
			auto &pre = Ask[i][j - 1], &cur = Ask[i][j];
			auto it = S.lower_bound(pre.x);
			if (it != S.end() && *it < cur.x) continue;
			E[++ec] = Edge(cur.x - pre.x, {pre.y, cur.y});
		}
		// clear the vectors
		Ask[i].clear(); Evt[i].clear();
	}
}

struct dsu {
	int d[maxn];
	void init() { for (int i = 1; i <= N; ++i) d[i] = -1; }
	int find(int i) { return (d[i] < 0 ? i : (d[i] = find(d[i]))); }
	bool same(int i, int j) { return find(i) == find(j); }
	void join(int i, int j) {
		if (same(i, j)) return;
		i = find(i), j = find(j);
		d[i] += d[j]; d[j] = i;
	}
} D;

int span[maxn], sc = 0;
ll spanSum[maxn], ans[3 * maxn];
vector<int> queries[maxn];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N >> M >> C;
	for (int i = 1; i <= N; ++i) cin >> P[i].x >> P[i].y;
	for (int i = 1; i <= M; ++i) cin >> RA[i].x >> RA[i].y >> RB[i].x >> RB[i].y;
	build_edges();
	for (int i = 1; i <= N; ++i) swap(P[i].x, P[i].y);
	for (int i = 1; i <= M; ++i) swap(RA[i].x, RA[i].y), swap(RB[i].x, RB[i].y);
	build_edges();
	D.init();
	sort(E + 1, E + ec + 1);
	for (int i = 1; i <= ec; ++i) {
		int u = E[i].y.x, v = E[i].y.y, w = E[i].x;
		// cout << u << ' ' << v << ' ' << w << endl;
		if (!D.same(u, v)) {
			span[++sc] = i; spanSum[sc] = w; D.join(u, v);
		}
	}
	for (int i = 1; i <= C; ++i) {
		cin >> B[i] >> H[i];
		queries[upper_bound(spanSum + 1, spanSum + sc + 1, B[i]) - spanSum - 1].push_back(i);
	}
	for (int i = 1; i <= sc; ++i) spanSum[i] += spanSum[i - 1];
	for (int i = 0; i <= sc; ++i) {
		for (auto &u: queries[i]) {
			if (H[u] >= N - i) ans[u] = spanSum[i] + (N - i) * 1LL * B[u];
			else {
				if (N - sc > H[u]) ans[u] = -1;
				else ans[u] = spanSum[N - H[u]] + H[u] * 1LL * B[u];
			}
		}
	}
	for (int i = 1; i <= C; ++i) printf("%lld\n", ans[i]);
}

Compilation message (stderr)

construction.cpp: In function 'void build_edges()':
construction.cpp:48:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < Ask[i].size(); ++j) {
                     ^

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30