Submission #921940

#	Time	Username	Problem	Language	Result	Execution time	Memory
921940		Nonoze	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	41 ms	9344 KiB

bridge

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long long ll;


#define int long long
#define sz(x) (int)(x.size())
#define debug(x) cerr << (#x) << ": " << (x) << endl
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

struct traj {
	int l, r;
	double mid;
};

vector<traj> a;
int n, k, m;
int calcres(int mid) {
	vector<int> vec1, vec2;
	for (int i=0; i<=mid; i++) {
		vec1.push_back(a[i].l);
		vec1.push_back(a[i].r);
	}
	for (int i=mid+1; i<n; i++) {
		vec2.push_back(a[i].l);
		vec2.push_back(a[i].r);
	}
	int ans=0;
	if (!vec1.empty()) {
		sort(all(vec1));
		int bridge=vec1[sz(vec1)/2-1];
		for (int i=0; i<=mid; i++) {
			ans+=abs(a[i].l-bridge)+abs(a[i].r-bridge);
		}
	}
	if (!vec2.empty()) {
		sort(all(vec2));
		int bridge=vec2[sz(vec2)/2-1];
		for (int i=mid+1; i<n; i++) {
			ans+=abs(a[i].l-bridge)+abs(a[i].r-bridge);
		}
	}
	// cout << mid << " " << ans << endl;
	return ans;
}


int trinary_search(int l, int r) {
	if (r-l<10) {
		int ans=LLONG_MAX;
		for (int i=l; i<=r; i++) {
			ans=min(ans, calcres(i));
		}
		return ans;
	}
	int m1=l+(r-l)/3;
	int m2=l+2*(r-l)/3;
	int s1=calcres(m1);
	int s2=calcres(m2);
	if (s1<s2) return trinary_search(l, m2+1);
	else return trinary_search(m1-1, r);
}


void solve() {
	cin >> k >> n;
	int res=0;
	for (int i=0; i<n; i++) {
		char aa, bb;
		int aaa, bbb; cin >> aa >> aaa >> bb >> bbb;
		if (aa==bb) {
			res+=abs(aaa-bbb);
			continue;
		}
		if (aaa>bbb) swap(aaa, bbb);
		a.push_back(traj{aaa, bbb, (double)(aaa+bbb)/2.0});
	}
	n=sz(a);
	res+=n;
	if (n==0) {
		cout << res << endl;
		return;
	}
	sort(all(a), [](traj &A, traj &B){return A.mid<B.mid;});
	if (k==1) cout << res+calcres(n-1) << endl;
	else cout << res+trinary_search(0, n-1) << endl;
	return;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;// cin >> tt;
	while(tt--) solve();
	return 0;
}

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