oj.uz

Submission #787400

# Submission time Handle Problem Language Result Execution time Memory
787400 2023-07-19T06:52:37 Z 박영우(#10035) 도로 건설 사업 (JOI13_construction) C++17
100 / 100
 472 ms 32704 KB 
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1001010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<pair<int, pii>> hst, vst;
pii edges[MAX];
int W[MAX];
pii point[MAX];
int p[MAX];
int find(int a) {
	if (p[a] == a) return a;
	return p[a] = find(p[a]);
}
bool uni(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	p[a] = b;
	return true;
}
int cv[MAX];
ll psum[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, C;
	cin >> N >> M >> C;
	int i, a, b, c, d;
	for (i = 1; i <= N; i++) cin >> point[i].first >> point[i].second;
	for (i = 1; i <= M; i++) {
		cin >> a >> b >> c >> d;
		hst.emplace_back(b, pii(a, c));
		hst.emplace_back(d, pii(a, c));
		vst.emplace_back(a, pii(b, d));
		vst.emplace_back(c, pii(b, d));
	}
	sort(hst.begin(), hst.end());
	sort(vst.begin(), vst.end());
	map<int, int> mp;
	vector<int> v;
	for (i = 1; i <= N; i++) v.push_back(i);
	sort(v.begin(), v.end(), [&](int a, int b) {return point[a].first < point[b].first; });
	int cnt = 0, ptr;
	ptr = 0;
	for (auto x : v) {
		while (ptr < M * 2 && point[x].first >= vst[ptr].first) {
			auto [l, r] = vst[ptr++].second;
			while (1) {
				auto it = mp.lower_bound(l);
				if (it == mp.end()) break;
				if (it->first > r) break;
				mp.erase(it);
			}
		}
		if (mp.find(point[x].second) != mp.end()) edges[++cnt] = pii(x, mp[point[x].second]);
		mp[point[x].second] = x;
	}
	mp.clear();
	sort(v.begin(), v.end(), [&](int a, int b) {return point[a].second < point[b].second; });
	ptr = 0;
	for (auto x : v) {
		while (ptr < M * 2 && point[x].second >= hst[ptr].first) {
			auto [l, r] = hst[ptr++].second;
			while (1) {
				auto it = mp.lower_bound(l);
				if (it == mp.end()) break;
				if (it->first > r) break;
				mp.erase(it);
			}
		}
		if (mp.find(point[x].first) != mp.end()) edges[++cnt] = pii(x, mp[point[x].first]);
		mp[point[x].first] = x;
	}
	for (i = 1; i <= cnt; i++) W[i] = abs(point[edges[i].first].first - point[edges[i].second].first) + abs(point[edges[i].first].second - point[edges[i].second].second);
	for (i = 1; i <= N; i++) p[i] = i;
	vector<int> ev;
	for (i = 1; i <= cnt; i++) ev.push_back(i);
	sort(ev.begin(), ev.end(), [&](int a, int b) {return W[a] < W[b]; });
	int ecnt = 0;
	for (auto e : ev) if (uni(edges[e].first, edges[e].second)) cv[++ecnt] = W[e], psum[ecnt] = psum[ecnt - 1] + cv[ecnt];
	int h;
	while (C--) {
		cin >> b >> h;
		if (ecnt + h < N) {
			cout << -1 << ln;
			continue;
		}
		int ind = lower_bound(cv + 1, cv + ecnt + 1, b) - cv;
		ind = max(ind, N - h + 1);
		ll ans = 1ll * (N - ind + 1) * b;
		ans += psum[ind - 1];
		cout << ans << ln;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1064 KB Output is correct
2 Correct 240 ms 8748 KB Output is correct
3 Correct 234 ms 10616 KB Output is correct
4 Correct 221 ms 13984 KB Output is correct
5 Correct 276 ms 15916 KB Output is correct
6 Correct 251 ms 10712 KB Output is correct
7 Correct 131 ms 14364 KB Output is correct
8 Correct 138 ms 20648 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1064 KB Output is correct
2 Correct 240 ms 8748 KB Output is correct
3 Correct 234 ms 10616 KB Output is correct
4 Correct 221 ms 13984 KB Output is correct
5 Correct 276 ms 15916 KB Output is correct
6 Correct 251 ms 10712 KB Output is correct
7 Correct 131 ms 14364 KB Output is correct
8 Correct 138 ms 20648 KB Output is correct
9 Correct 311 ms 15944 KB Output is correct
10 Correct 306 ms 15892 KB Output is correct
11 Correct 312 ms 15936 KB Output is correct
12 Correct 307 ms 15936 KB Output is correct
13 Correct 314 ms 16800 KB Output is correct
14 Correct 310 ms 15652 KB Output is correct
15 Correct 330 ms 15656 KB Output is correct
16 Correct 252 ms 25936 KB Output is correct
17 Correct 269 ms 26296 KB Output is correct
18 Correct 268 ms 27580 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1064 KB Output is correct
2 Correct 240 ms 8748 KB Output is correct
3 Correct 234 ms 10616 KB Output is correct
4 Correct 221 ms 13984 KB Output is correct
5 Correct 276 ms 15916 KB Output is correct
6 Correct 251 ms 10712 KB Output is correct
7 Correct 131 ms 14364 KB Output is correct
8 Correct 138 ms 20648 KB Output is correct
9 Correct 392 ms 22500 KB Output is correct
10 Correct 394 ms 18808 KB Output is correct
11 Correct 364 ms 17152 KB Output is correct
12 Correct 305 ms 20008 KB Output is correct
13 Correct 373 ms 14660 KB Output is correct
14 Correct 472 ms 24868 KB Output is correct
15 Correct 411 ms 20316 KB Output is correct
16 Correct 378 ms 19280 KB Output is correct
17 Correct 253 ms 21324 KB Output is correct
18 Correct 302 ms 27596 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1064 KB Output is correct
2 Correct 240 ms 8748 KB Output is correct
3 Correct 234 ms 10616 KB Output is correct
4 Correct 221 ms 13984 KB Output is correct
5 Correct 276 ms 15916 KB Output is correct
6 Correct 251 ms 10712 KB Output is correct
7 Correct 131 ms 14364 KB Output is correct
8 Correct 138 ms 20648 KB Output is correct
9 Correct 311 ms 15944 KB Output is correct
10 Correct 306 ms 15892 KB Output is correct
11 Correct 312 ms 15936 KB Output is correct
12 Correct 307 ms 15936 KB Output is correct
13 Correct 314 ms 16800 KB Output is correct
14 Correct 310 ms 15652 KB Output is correct
15 Correct 330 ms 15656 KB Output is correct
16 Correct 252 ms 25936 KB Output is correct
17 Correct 269 ms 26296 KB Output is correct
18 Correct 268 ms 27580 KB Output is correct
19 Correct 392 ms 22500 KB Output is correct
20 Correct 394 ms 18808 KB Output is correct
21 Correct 364 ms 17152 KB Output is correct
22 Correct 305 ms 20008 KB Output is correct
23 Correct 373 ms 14660 KB Output is correct
24 Correct 472 ms 24868 KB Output is correct
25 Correct 411 ms 20316 KB Output is correct
26 Correct 378 ms 19280 KB Output is correct
27 Correct 253 ms 21324 KB Output is correct
28 Correct 302 ms 27596 KB Output is correct
29 Correct 416 ms 21872 KB Output is correct
30 Correct 335 ms 14444 KB Output is correct
31 Correct 448 ms 15592 KB Output is correct
32 Correct 286 ms 10156 KB Output is correct
33 Correct 401 ms 15712 KB Output is correct
34 Correct 272 ms 9876 KB Output is correct
35 Correct 396 ms 15732 KB Output is correct
36 Correct 416 ms 20868 KB Output is correct
37 Correct 355 ms 32704 KB Output is correct
38 Correct 356 ms 29108 KB Output is correct
39 Correct 285 ms 27568 KB Output is correct