Submission #321580

#	Time	Username	Problem	Language	Result	Execution time	Memory
321580		binary_python	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	288 ms	16224 KiB

bridge

#include <bits/stdc++.h>
#define ll long long
using namespace std;


#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using Tree= tree<T, null_type, less<T>,rb_tree_tag, tree_order_statistics_node_update>;

int main() {
	int k,n;
	cin >> k >> n;
	if (k==1) {
		ll ans = 0; 
		vector<int> nums;
		Tree<pair<int,int>> ms;
		int c=0;
		for (int i=0; i<n; i++) {
			char p,q; int s,t;
			cin >> p >> s >> q >> t;
			if (p == q) {
				ans += abs(t-s);
			}
			else {
				nums.push_back(s);
				nums.push_back(t);
				ms.insert({s,i}); ms.insert({t,i+n});
				c+=2;
			}
		}
		int median = ms.find_by_order(c/2)->first;
		for (int z : nums) {ans += abs(z-median);}
		ans += (c/2);
		cout << ans << "\n";
	}
	
	
	
	
	return 0;
}

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