oj.uz

Submission #637021

# Submission time Handle Problem Language Result Execution time Memory
637021 2022-08-31T07:33:28 Z SharpEdged Palembang Bridges (APIO15_bridge) C++17
100 / 100
 381 ms 13592 KB 
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define LSB(x) ((x) & -(x))
#define sz(x) ((int)x.size())

using namespace std;

typedef long long ll;

const char nl = '\n';

struct OrderedSet{
	multiset<ll> lo, hi;
	ll cost = 0;
	ll m;
	OrderedSet() {}
	void Insert(ll x){
		m = (sz(lo) > 0) ? *lo.rbegin() : x;
		cost += abs(x - m);
		if (x <= m) lo.insert(x);
		else hi.insert(x);
		Balance();
	}
	
	void Erase(ll x){
		m = *lo.rbegin();
		cost -= abs(x - m);
		if (x <= m) lo.erase(lo.find(x));
		else hi.erase(hi.find(x));
		Balance();
	}
	
	void Balance(){
		ll l = sz(lo)-1, r = sz(hi), new_m = m;
		if (sz(hi) > sz(lo)){
			ll val = *hi.begin();
			hi.erase(hi.begin());
			lo.insert(val);
			new_m = *lo.rbegin();
			cost += (new_m - m) * (l + 1 - r);
		}
		else if (sz(hi) < sz(lo) - 1){
			ll val = *lo.rbegin();
			lo.erase(lo.find(val));
			hi.insert(val);
			new_m = *lo.rbegin();
			cost += (m - new_m) * (r + 1 - l);
		}
		m = new_m;
	}
};

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int k, n; cin >> k >> n;
	ll base = 0;
	vector<pair<ll, ll>> v;
	for (int i = 0; i < n; i++){
		char z1, z2; ll p1, p2;
		cin >> z1 >> p1 >> z2 >> p2;
		if (z1 == z2) base += abs(p1 - p2);
		else {
			v.eb(p1, p2);
			base++;
		}
	}
	auto comp = [&](const pair<ll, ll> &a, const pair<ll, ll> &b) -> bool { return a.f+a.s < b.f+b.s; };
	sort(all(v), comp);
	OrderedSet sL, sR;
	for (int i = 0; i < sz(v); i++){
		sR.Insert(v[i].f);
		sR.Insert(v[i].s);
	}
	ll ans = sR.cost;
	if (k == 1) { cout << base + ans << nl; return 0; }
	for (int i = 0; i < sz(v); i++){
		sR.Erase(v[i].f);
		sR.Erase(v[i].s);
		sL.Insert(v[i].f);
		sL.Insert(v[i].s);
		ans = min(ans, sL.cost + sR.cost);
	}
	cout << base + ans << nl;
	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 78 ms 11148 KB Output is correct
13 Correct 131 ms 11232 KB Output is correct
14 Correct 133 ms 10044 KB Output is correct
15 Correct 56 ms 6728 KB Output is correct
16 Correct 86 ms 11176 KB Output is correct
17 Correct 88 ms 11156 KB Output is correct
18 Correct 70 ms 11196 KB Output is correct
19 Correct 85 ms 11204 KB Output is correct
20 Correct 83 ms 11204 KB Output is correct
21 Correct 87 ms 11236 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 2 ms 344 KB Output is correct
15 Correct 2 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 324 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 464 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 3 ms 328 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 178 ms 11948 KB Output is correct
26 Correct 249 ms 12224 KB Output is correct
27 Correct 315 ms 12908 KB Output is correct
28 Correct 308 ms 13508 KB Output is correct
29 Correct 381 ms 13592 KB Output is correct
30 Correct 119 ms 7248 KB Output is correct
31 Correct 154 ms 12896 KB Output is correct
32 Correct 195 ms 13484 KB Output is correct
33 Correct 121 ms 13176 KB Output is correct
34 Correct 178 ms 13504 KB Output is correct
35 Correct 177 ms 13148 KB Output is correct
36 Correct 185 ms 13244 KB Output is correct
37 Correct 185 ms 12020 KB Output is correct