Submission #853075

#	Time	Username	Problem	Language	Result	Execution time	Memory
853075		aymanrs	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2011 ms	4436 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int k, n, a, b;cin >> k >> n;
	char c,h;
	long long sl = 0, ans = LONG_LONG_MAX, cur = 0, tans = 0;
	vector<pair<int, int>> e;
	if(k == 1){
		while(n--){
		cin >> c >> a >> h >> b;
		if(a>b)swap(a,b);
		tans += b-a;
		if(c==h) continue;
		tans++;
		e.emplace_back(a, false);
		e.emplace_back(b, true);
	}
	if(e.empty()){
		cout << tans << '\n';
		return;
	}
	sort(e.begin(), e.end());
	for(int i = 0;i < e.size();i++){
		if(!e[i].second) {
			sl -= 2;
			cur += 2*(e[i].first-e[0].first);
		}
	}
	int pr = e[0].first;
	for(auto p : e){
		cur += sl*(p.first-pr);
		pr = p.first;
		ans = min(ans, cur);
		sl += 2;
	}
	cout << ans+tans << '\n';
	return;
	}
	for(int i = 0;i < n;i++){
		cin >> c >> a >> h >> b;
		if(a>b)swap(a,b);
		tans += b-a;
		if(c==h) continue;
		tans++;
		e.emplace_back(a, -i-1);
		e.emplace_back(b, i+1);
	}
	if(e.empty()){
		cout << tans << '\n';
		return;
	}
	sort(e.begin(), e.end());
	int pr = e[0].first;
	for(auto p : e){
		cur += sl*(p.first-pr);
		pr = p.first;
		if(p.second > 0) sl += 2;
		vector<pair<int, int>> g;
		int v[n+1];fill(v, v+n+1, -1);
		long long slope = 0, CUR = 0;
		for(auto pp : e){
			if(pp.first <= p.first) continue;
			if(pp.second < 0){
				CUR += 2*(pp.first-p.first);
				slope -= 2;
				g.emplace_back(pp.first, 2);
				v[-pp.second] = pp.first-p.first;
			} else if(v[pp.second] != -1){
				g.emplace_back(pp.first, 2);
				g.emplace_back(pp.first+v[pp.second], -2);
			}
		}
		if(g.empty()){
			ans = min(ans, cur);
			continue;
		}
		sort(g.begin(), g.end());
		int pre = p.first;
		for(auto pp : g){
			CUR += slope*(pp.first-pre);
			pre = pp.first;
			ans = min(ans, cur+CUR);
			slope += pp.second;
		}
	}
	cout << ans+tans << '\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Compilation message (stderr)

bridge.cpp: In function 'void solve()':
bridge.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i = 0;i < e.size();i++){
      |                ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 0 / 37