제출 #1281326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281326		Jawad_Akbar_JJ	Palembang Bridges (APIO15_bridge)	C++20	63 / 100	2095 ms	8176 KiB

bridge

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
#define int long long

int get(vector<pair<int,int>> vc, int l, int r, int Ans = 0){
	for (int i=0;i<vc.size();i++){
		if (vc[i].second <= l)
			Ans += (l - vc[i].second);
		else if (vc[i].first >= r)
			Ans += (vc[i].first - r);
		else if (l <= vc[i].first and r >= vc[i].second)
			Ans += min(vc[i].first - l,r - vc[i].second);
	}
	return Ans * 2;
}

signed main(){
	int k, n, Ans = 0, Sumr = 0, finalAns = 1e17;
	cin>>k>>n;

	vector<pair<int,int>> vec;
	vector<int> pnt;
	for (int i=1;i<=n;i++){
		char a, c;
		int b, d;
		cin>>a>>b>>c>>d;
		if (b > d)
			swap(b, d);

		if (a == c)
			Ans += d - b;
		else{
			vec.push_back({b, d});
			pnt.push_back(b);
			pnt.push_back(d);
			Ans += d - b + 1;
			Sumr += b + 1;
		}
	}

	sort(begin(vec), end(vec));
	sort(begin(pnt), end(pnt));
	pnt.resize(unique(begin(pnt), end(pnt)) - begin(pnt));

	finalAns = Ans + Sumr * 2;
	if (k == 1){
		int Rgt = vec.size(), Lft = 0, Suml = 0, id = 0, lst = -1;
		multiset<int> st;

		for (int i : pnt){
			Sumr -= Rgt * (i - lst);
			Suml += Lft * (i - lst);

			while (id < vec.size() and vec[id].first == i)
				st.insert(vec[id].second), id++, Rgt--;

			while (st.size() > 0 and *begin(st) == i)
				Lft++, st.erase(begin(st));
			// cout<<i<<" | "<<Lft<<" "<<Suml<<" | "<<Rgt<<" "<<Sumr<<endl;
			lst = i;
			finalAns = min(finalAns, Ans + (Suml + Sumr) * 2);
		}
		return cout<<finalAns<<endl, 0;
	}

	for (int l=0, r=0;l<pnt.size();l++){
		int cur = get(vec, pnt[l], pnt[r]);
		while (r + 1 < pnt.size()){
			int Nw = get(vec, pnt[l], pnt[r + 1]);
			if (Nw <= cur)
				cur = Nw, r++;
			else
				break;
		}
		finalAns = min(finalAns, cur + Ans);
		// cout<<l<<" "<<r<<" "<<cur<<endl;
	}
	cout<<finalAns<<'\n';
}

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