Submission #1281323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281323		Jawad_Akbar_JJ	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	117 ms	8204 KiB

bridge

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

using namespace std;
#define int long long

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));

	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;
	}
}

/*

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7


*/

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