oj.uz

Submission #48200

# Submission time Handle Problem Language Result Execution time Memory
48200 2018-05-10T13:57:37 Z E869120 Palembang Bridges (APIO15_bridge) C++14
100 / 100
 1881 ms 20308 KB 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

long long N, K, Q, A[100009], B[100009], sum;
vector<long long>Z; vector<long long>S;

long long calculate() {
	long long rem = 0;
	for (int i = 1; i <= Q; i++) {
		long long F = (1LL << 60);
		for (int j = 0; j < S.size(); j++) {
			if (A[i] <= S[j] && S[j] <= B[i]) F = 0;
			F = min(F, 2LL * min(abs(A[i] - S[j]), abs(B[i] - S[j])));
		}
		rem += F;
	}
	return sum + rem;
}

long long solve(long long pos) {
	long long rev = (1LL << 60); int i = pos;

	vector<pair<long long, long long>>vec; long long R = 0;
	for (int j = 1; j <= Q; j++) {
		if (A[j] > Z[i]) { R += 2; vec.push_back(make_pair(A[j], 2)); vec.push_back(make_pair(B[j], 2)); vec.push_back(make_pair(B[j] + A[j] - Z[i], -2)); }
	}
	sort(vec.begin(), vec.end());

	S = vector<long long>{ Z[i] };
	long long D = calculate(), J = -R, cx = Z[i]; rev = min(rev, D);
	for (int j = 0; j < vec.size(); j++) {
		rev = min(rev, D);
		D += J*(vec[j].first - cx);
		J += vec[j].second; cx = vec[j].first;
	}
	return rev;
}

int main() {
	cin >> K >> N;
	for (int i = 1; i <= N; i++) {
		char a1, b1; long long a2, b2;
		cin >> a1 >> a2 >> b1 >> b2;
		if (a1 == b1) sum += abs(a2 - b2);
		else {
			Q++; if (a2 > b2) swap(a2, b2);
			A[Q] = a2; B[Q] = b2;
			sum += (b2 - a2 + 1);
		}
	}
	for (int i = 1; i <= Q; i++) { Z.push_back(A[i]); Z.push_back(B[i]); }
	sort(Z.begin(), Z.end());
	if (Q == 0) {
		cout << sum << endl;
		return 0;
	}
	if (K == 1) {
		vector<long long>vec;
		for (int i = 1; i <= Q; i++) { vec.push_back(A[i]); vec.push_back(B[i]); }
		sort(vec.begin(), vec.end());
		
		S = vector<long long>{ vec[vec.size() / 2] };
		long long ans = calculate();
		cout << ans << endl;
	}
	if (K == 2) {
		long long ans = (1LL << 60);
		long long L = 0, R = Z.size(), C1, C2;

		for (int i = 0; i < 27; i++) {
			C1 = (L + L + R) / 3;
			C2 = (L + R + R) / 3;
			long long v1 = solve(C1);
			long long v2 = solve(C2);
			ans = min(ans, min(v1, v2));
			if (v1 > v2) { L = C1; }
			else { R = C2; }
		}
		for (int i = -3; i <= 3; i++) {
			if (C1 + i < 0 || C1 + i >= Z.size()) continue;
			ans = min(ans, solve(C1 + i));
		}
		cout << ans << endl;
	}
	return 0;
}

Compilation message

bridge.cpp: In function 'long long int calculate()':
bridge.cpp:14:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < S.size(); j++) {
                   ~~^~~~~~~~~~
bridge.cpp: In function 'long long int solve(long long int)':
bridge.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < vec.size(); j++) {
                  ~~^~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:83:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (C1 + i < 0 || C1 + i >= Z.size()) continue;
                      ~~~~~~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 3 ms 592 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 3 ms 592 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 3 ms 592 KB Output is correct
11 Correct 3 ms 592 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 648 KB Output is correct
4 Correct 4 ms 648 KB Output is correct
5 Correct 4 ms 648 KB Output is correct
6 Correct 3 ms 648 KB Output is correct
7 Correct 4 ms 648 KB Output is correct
8 Correct 3 ms 648 KB Output is correct
9 Correct 3 ms 648 KB Output is correct
10 Correct 3 ms 648 KB Output is correct
11 Correct 3 ms 648 KB Output is correct
12 Correct 71 ms 6760 KB Output is correct
13 Correct 164 ms 6760 KB Output is correct
14 Correct 108 ms 6760 KB Output is correct
15 Correct 94 ms 6760 KB Output is correct
16 Correct 107 ms 6760 KB Output is correct
17 Correct 136 ms 6844 KB Output is correct
18 Correct 131 ms 6844 KB Output is correct
19 Correct 158 ms 6888 KB Output is correct
20 Correct 119 ms 6888 KB Output is correct
21 Correct 160 ms 6888 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6888 KB Output is correct
2 Correct 2 ms 6888 KB Output is correct
3 Correct 2 ms 6888 KB Output is correct
4 Correct 2 ms 6888 KB Output is correct
5 Correct 2 ms 6888 KB Output is correct
6 Correct 2 ms 6888 KB Output is correct
7 Correct 2 ms 6888 KB Output is correct
8 Correct 2 ms 6888 KB Output is correct
9 Correct 3 ms 6888 KB Output is correct
10 Correct 3 ms 6888 KB Output is correct
11 Correct 2 ms 6888 KB Output is correct
12 Correct 2 ms 6888 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6888 KB Output is correct
2 Correct 2 ms 6888 KB Output is correct
3 Correct 2 ms 6888 KB Output is correct
4 Correct 3 ms 6888 KB Output is correct
5 Correct 2 ms 6888 KB Output is correct
6 Correct 2 ms 6888 KB Output is correct
7 Correct 2 ms 6888 KB Output is correct
8 Correct 3 ms 6888 KB Output is correct
9 Correct 3 ms 6888 KB Output is correct
10 Correct 3 ms 6888 KB Output is correct
11 Correct 2 ms 6888 KB Output is correct
12 Correct 3 ms 6888 KB Output is correct
13 Correct 4 ms 6888 KB Output is correct
14 Correct 11 ms 6888 KB Output is correct
15 Correct 10 ms 6888 KB Output is correct
16 Correct 2 ms 6888 KB Output is correct
17 Correct 6 ms 6888 KB Output is correct
18 Correct 4 ms 6888 KB Output is correct
19 Correct 3 ms 6888 KB Output is correct
20 Correct 10 ms 6888 KB Output is correct
21 Correct 12 ms 6888 KB Output is correct
22 Correct 14 ms 6888 KB Output is correct
23 Correct 6 ms 6888 KB Output is correct
24 Correct 14 ms 6888 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6888 KB Output is correct
2 Correct 2 ms 6888 KB Output is correct
3 Correct 2 ms 6888 KB Output is correct
4 Correct 2 ms 6888 KB Output is correct
5 Correct 2 ms 6888 KB Output is correct
6 Correct 2 ms 6888 KB Output is correct
7 Correct 2 ms 6888 KB Output is correct
8 Correct 2 ms 6888 KB Output is correct
9 Correct 2 ms 6888 KB Output is correct
10 Correct 3 ms 6888 KB Output is correct
11 Correct 2 ms 6888 KB Output is correct
12 Correct 2 ms 6888 KB Output is correct
13 Correct 4 ms 6888 KB Output is correct
14 Correct 11 ms 6888 KB Output is correct
15 Correct 10 ms 6888 KB Output is correct
16 Correct 3 ms 6888 KB Output is correct
17 Correct 6 ms 6888 KB Output is correct
18 Correct 4 ms 6888 KB Output is correct
19 Correct 3 ms 6888 KB Output is correct
20 Correct 12 ms 6888 KB Output is correct
21 Correct 11 ms 6888 KB Output is correct
22 Correct 14 ms 6888 KB Output is correct
23 Correct 8 ms 6888 KB Output is correct
24 Correct 14 ms 6888 KB Output is correct
25 Correct 379 ms 7024 KB Output is correct
26 Correct 1090 ms 11224 KB Output is correct
27 Correct 1402 ms 11264 KB Output is correct
28 Correct 1404 ms 11264 KB Output is correct
29 Correct 1376 ms 11276 KB Output is correct
30 Correct 677 ms 11276 KB Output is correct
31 Correct 124 ms 11276 KB Output is correct
32 Correct 1275 ms 11808 KB Output is correct
33 Correct 1615 ms 16804 KB Output is correct
34 Correct 1881 ms 16804 KB Output is correct
35 Correct 1016 ms 16804 KB Output is correct
36 Correct 1756 ms 20308 KB Output is correct
37 Correct 90 ms 20308 KB Output is correct