oj.uz

Submission #260945

# Submission time Handle Problem Language Result Execution time Memory
260945 2020-08-11T08:21:45 Z atoiz Palembang Bridges (APIO15_bridge) C++14
100 / 100
 361 ms 13840 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <cassert>

using namespace std;

struct Balancer
{
	multiset<int> lef, rig;
	int cntLef, cntRig;
	int64_t sumLef, sumRig;

	Balancer()
	{
		lef.clear(), rig.clear();
		cntLef = 0, cntRig = 0;
		sumLef = 0, sumRig = 0;
	}

	void add(int l, int r)
	{
		// cout << "add " << l << ' ' << r << endl;
		l = l << 1, r = r << 1 | 1;
		int mid = (!lef.empty() ? *lef.rbegin() : 0);

		if (l <= mid) lef.insert(l);
		else rig.insert(l), sumRig += l / 2, ++cntRig;

		if (r <= mid) lef.insert(r), sumLef += r / 2, ++cntLef;
		else rig.insert(r);

		while (((int) rig.size()) - ((int) lef.size()) > 1) {
			int x = *rig.begin();
			rig.erase(rig.begin());
			lef.insert(lef.end(), x);
			if (x & 1) sumLef += x / 2, ++cntLef;
			else sumRig -= x / 2, --cntRig;
		}

		while (((int) lef.size()) - ((int) rig.size()) > 1) {
			int x = *lef.rbegin();
			lef.erase(prev(lef.end()));
			rig.insert(rig.begin(), x);
			if (x & 1) sumLef -= x / 2, --cntLef;
			else sumRig += x / 2, ++cntRig;
		}
	}

	int64_t get()
	{
		if (lef.empty() && rig.empty()) return 0;
		int64_t mid = (lef.empty() ? *rig.begin() : *lef.rbegin());
		// cout << "get " << (cntLef - cntRig) * mid - sumLef + sumRig << endl;
		return (cntLef - cntRig) * mid - sumLef + sumRig;
	}
};

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int K, M;
	cin >> K >> M;
	vector<pair<int, int>> vec;
	int64_t offset = 0;
	while (M--) {
		char cA, cB;
		int valA, valB;
		cin >> cA >> valA >> cB >> valB;
		if (valA > valB) swap(valA, valB);
		offset += valB - valA;
		if (cA != cB) vec.emplace_back(valA, valB);
	}

	M = (int) vec.size();
	offset += M;
	sort(vec.begin(), vec.end(), [&](pair<int, int> p, pair<int, int> q) { return p.first + p.second < q.first + q.second; });

	if (M == 0) return cout << offset << endl, 0;

	vector<int64_t> pref(M, 0);
	Balancer bal;
	for (int i = 0; i < M; ++i) {
		bal.add(vec[i].first, vec[i].second);
		pref[i] = bal.get();
	}

	int64_t ans = pref[M - 1];
	if (K == 1) return cout << offset + 2 * ans << endl, 0;

	bal = Balancer();
	for (int i = M - 1; i > 0; --i) {
		bal.add(vec[i].first, vec[i].second);
		ans = min(ans, bal.get() + pref[i - 1]);
	}
	cout << offset + 2 * ans << endl;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 71 ms 12140 KB Output is correct
13 Correct 182 ms 13296 KB Output is correct
14 Correct 137 ms 11372 KB Output is correct
15 Correct 83 ms 8180 KB Output is correct
16 Correct 78 ms 12984 KB Output is correct
17 Correct 95 ms 13540 KB Output is correct
18 Correct 81 ms 13424 KB Output is correct
19 Correct 101 ms 13292 KB Output is correct
20 Correct 90 ms 13164 KB Output is correct
21 Correct 100 ms 13292 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

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

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 512 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 2 ms 512 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 119 ms 12144 KB Output is correct
26 Correct 223 ms 12268 KB Output is correct
27 Correct 329 ms 13040 KB Output is correct
28 Correct 347 ms 13676 KB Output is correct
29 Correct 361 ms 13676 KB Output is correct
30 Correct 117 ms 7412 KB Output is correct
31 Correct 119 ms 12996 KB Output is correct
32 Correct 138 ms 13592 KB Output is correct
33 Correct 113 ms 13268 KB Output is correct
34 Correct 144 ms 13840 KB Output is correct
35 Correct 139 ms 13264 KB Output is correct
36 Correct 144 ms 13516 KB Output is correct
37 Correct 123 ms 12144 KB Output is correct