oj.uz

Submission #34118

# Submission time Handle Problem Language Result Execution time Memory
34118 2017-11-07T15:28:55 Z natsukagami 도로 건설 사업 (JOI13_construction) C++14
100 / 100
 1539 ms 98124 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64568 KB Output is correct
2 Correct 319 ms 70112 KB Output is correct
3 Correct 323 ms 70112 KB Output is correct
4 Correct 299 ms 68660 KB Output is correct
5 Correct 326 ms 70112 KB Output is correct
6 Correct 313 ms 70112 KB Output is correct
7 Correct 176 ms 67472 KB Output is correct
8 Correct 253 ms 73276 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1363 ms 88592 KB Output is correct
2 Correct 1263 ms 88592 KB Output is correct
3 Correct 1236 ms 88592 KB Output is correct
4 Correct 1206 ms 88592 KB Output is correct
5 Correct 753 ms 79088 KB Output is correct
6 Correct 306 ms 70112 KB Output is correct
7 Correct 1203 ms 88592 KB Output is correct
8 Correct 343 ms 77304 KB Output is correct
9 Correct 359 ms 76812 KB Output is correct
10 Correct 863 ms 98124 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 73864 KB Output is correct
2 Correct 633 ms 74244 KB Output is correct
3 Correct 636 ms 74072 KB Output is correct
4 Correct 443 ms 72032 KB Output is correct
5 Correct 559 ms 73552 KB Output is correct
6 Correct 716 ms 74468 KB Output is correct
7 Correct 636 ms 74204 KB Output is correct
8 Correct 569 ms 73544 KB Output is correct
9 Correct 339 ms 71644 KB Output is correct
10 Correct 559 ms 75680 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1419 ms 91672 KB Output is correct
2 Correct 893 ms 82980 KB Output is correct
3 Correct 1439 ms 90900 KB Output is correct
4 Correct 519 ms 73812 KB Output is correct
5 Correct 1386 ms 91460 KB Output is correct
6 Correct 546 ms 74332 KB Output is correct
7 Correct 1323 ms 94108 KB Output is correct
8 Correct 1539 ms 90752 KB Output is correct
9 Correct 526 ms 80160 KB Output is correct
10 Correct 1076 ms 98124 KB Output is correct
11 Correct 593 ms 76508 KB Output is correct