oj.uz

Submission #142681

# Submission time Handle Problem Language Result Execution time Memory
142681 2019-08-10T12:54:11 Z gs18103 도로 건설 사업 (JOI13_construction) C++14
100 / 100
 934 ms 56756 KB 
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false); cin.tie(0)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back
#define fi first
#define se second
#define G(tp, x) get<(x)>(tp)
#define INF 2000000000
#define LINF 1000000000000000000LL

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef tuple <int, int, int> tp3;

vector <pii> g[202020];
vector <tp3> arr, rx, ry;

int main() {
	fastio;
	int n, m, c;
	cin >> n >> m >> c;
	for(int i = 0, u, v; i < n; i++) {
		cin >> u >> v;
		arr.eb(u, v, i);
	}
	for(int i = 0, p, q, r, s; i < m; i++) {
		cin >> p >> q >> r >> s;
		rx.eb(p, q, i);
		rx.eb(r+1, q, i);
		ry.eb(q, r, i);
		ry.eb(s+1, r, i);
	}
	sort(all(arr));
	sort(all(rx));
	sort(all(ry));
	set <pii> setx, sety;
	int idx = 0;
	while(idx < 2*m && G(arr[0], 0) >= G(rx[idx], 0)) {
		if(setx.find({G(rx[idx], 1), G(rx[idx], 2)}) == setx.end()) {
			setx.insert({G(rx[idx], 1), G(rx[idx], 2)});
		}
		else setx.erase({G(rx[idx], 1), G(rx[idx], 2)});
		idx++;
	}
	for(int i = 1; i < n; i++) {
		if(G(arr[i], 0) == G(arr[i-1], 0)) {
			if(setx.lower_bound({G(arr[i], 1), -1}) == setx.lower_bound({G(arr[i-1], 1), -1})) {
				g[G(arr[i], 2)].eb(G(arr[i-1], 2), abs(G(arr[i-1], 1)-G(arr[i], 1)));
				g[G(arr[i-1], 2)].eb(G(arr[i], 2), abs(G(arr[i-1], 1)-G(arr[i], 1)));
			}
		}
		while(idx < 2*m && G(arr[i], 0) >= G(rx[idx], 0)) {
			if(setx.find({G(rx[idx], 1), G(rx[idx], 2)}) == setx.end()) {
				setx.insert({G(rx[idx], 1), G(rx[idx], 2)});
			}
			else setx.erase({G(rx[idx], 1), G(rx[idx], 2)});
			idx++;
		}
	}
	sort(all(arr), [](tp3 a, tp3 b) {
		if(G(a, 1) == G(b, 1)) return a < b;
		return G(a, 1) < G(b, 1);
	});
	idx = 0;
	while(idx < 2*m && G(arr[0], 1) >= G(ry[idx], 0)) {
		if(sety.find({G(ry[idx], 1), G(ry[idx], 2)}) == sety.end()) {
			sety.insert({G(ry[idx], 1), G(ry[idx], 2)});
		}
		else sety.erase({G(ry[idx], 1), G(ry[idx], 2)});
		idx++;
	}
	for(int i = 1; i < n; i++) {
		if(G(arr[i], 1) == G(arr[i-1], 1)) {
			if(sety.lower_bound({G(arr[i], 0), -1}) == sety.lower_bound({G(arr[i-1], 0), -1})) {
				g[G(arr[i], 2)].eb(G(arr[i-1], 2), abs(G(arr[i-1], 0)-G(arr[i], 0)));
				g[G(arr[i-1], 2)].eb(G(arr[i], 2), abs(G(arr[i-1], 0)-G(arr[i], 0)));
			}
		}
		while(idx < 2*m && G(arr[i], 1) >= G(ry[idx], 0)) {
			if(sety.find({G(ry[idx], 1), G(ry[idx], 2)}) == sety.end()) {
				sety.insert({G(ry[idx], 1), G(ry[idx], 2)});
			}
			else sety.erase({G(ry[idx], 1), G(ry[idx], 2)});
			idx++;
		}
	}

	int cnt = 0;
	vector <int> E;
	vector <ll> sum(2*n+10);
	vector <bool> chk(n+10);
	for(int i = 0; i < n; i++) {
		if(chk[i]) continue;
		cnt++;
		priority_queue <pii, vector <pii>, greater <pii> > pq;
		pq.push({0, i});
		while(!pq.empty()) {
			int x = pq.top().se;
			int val = pq.top().fi;
			pq.pop();
			if(chk[x]) continue;
			chk[x] = true;
			E.eb(val);
			for(auto j : g[x]) {
				pq.push({j.se, j.fi});
			}
		}
	}
	sort(all(E));
	sum[0] = E[0];
	for(int i = 1; i < E.size(); i++) {
		sum[i] = sum[i-1] + (ll)E[i];
	}
	while(c--) {
		ll b, h;
		cin >> b >> h;
		if(h < cnt) {
			cout << "-1\n";
			continue;
		}
		int k = (int)(upper_bound(all(E), b) - E.begin());
		if(E.size() - k + cnt <= h) {
			if(k == 0) cout << b * n << '\n';
			else cout << sum[k-1] + (E.size() - k + cnt) * b << '\n';
		}
		else {
			cout << sum[E.size()-h-1+cnt] + h * b << '\n';
		}
	}
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:113:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < E.size(); i++) {
                 ~~^~~~~~~~~~
construction.cpp:124:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(E.size() - k + cnt <= h) {
      ~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6028 KB Output is correct
2 Correct 204 ms 17632 KB Output is correct
3 Correct 199 ms 20712 KB Output is correct
4 Correct 429 ms 29288 KB Output is correct
5 Correct 293 ms 23620 KB Output is correct
6 Correct 208 ms 20820 KB Output is correct
7 Correct 248 ms 25544 KB Output is correct
8 Correct 196 ms 22600 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 23192 KB Output is correct
2 Correct 703 ms 23216 KB Output is correct
3 Correct 693 ms 23132 KB Output is correct
4 Correct 727 ms 23276 KB Output is correct
5 Correct 580 ms 24432 KB Output is correct
6 Correct 286 ms 20540 KB Output is correct
7 Correct 694 ms 34136 KB Output is correct
8 Correct 540 ms 40112 KB Output is correct
9 Correct 530 ms 40028 KB Output is correct
10 Correct 549 ms 47576 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 24828 KB Output is correct
2 Correct 481 ms 31976 KB Output is correct
3 Correct 423 ms 32488 KB Output is correct
4 Correct 606 ms 34616 KB Output is correct
5 Correct 340 ms 29536 KB Output is correct
6 Correct 513 ms 37848 KB Output is correct
7 Correct 480 ms 35868 KB Output is correct
8 Correct 453 ms 34868 KB Output is correct
9 Correct 435 ms 37076 KB Output is correct
10 Correct 454 ms 33668 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 31060 KB Output is correct
2 Correct 543 ms 28752 KB Output is correct
3 Correct 848 ms 43488 KB Output is correct
4 Correct 319 ms 26300 KB Output is correct
5 Correct 853 ms 43892 KB Output is correct
6 Correct 341 ms 27324 KB Output is correct
7 Correct 763 ms 43176 KB Output is correct
8 Correct 934 ms 48320 KB Output is correct
9 Correct 739 ms 51636 KB Output is correct
10 Correct 761 ms 56756 KB Output is correct
11 Correct 500 ms 34904 KB Output is correct