Submission #477292

#	Time	Username	Problem	Language	Result	Execution time	Memory
477292		ymm	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	48 ms	1940 KiB

bridge

///
///   ♪ Let the voice of love take you higher! ♪
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define F first
#define S second
typedef long long ll;
typedef std::pair<ll,ll> pll;
using namespace std;

ll inf = 1e9+100;
const int N = 100010;
pll a[N];
int k, n;

ll get(int l, int r, int x)
{
	ll ans = 0;
	Loop(i,l,r)
		ans += abs(a[i].F-x)+abs(a[i].S-x);
	return ans;
}

ll bin1(int L, int R)
{
	ll l = 0, r = inf;
	while(l < r)
	{
		ll m = (l+r)/2;
		ll v1 = get(L,R,m);
		ll v2 = get(L,R,m+1);
		if(v1 < v2) r = m;
		else        l = m+1;
	}
	return get(L,R,l);
}

ll bin2()
{
	int l = 0, r = n;
	while(l < r)
	{
		int m = (l+r)/2;
		ll v1 = bin1(0,m)+bin1(m,n);
		ll v2 = bin1(0,m+1)+bin1(m+1,n);
		if(v1 < v2) r = m;
		else        l = m+1;
	}
	return bin1(0,l)+bin1(l,n);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	#ifndef EVAL
	freopen("in.txt", "r", stdin);
	#endif
	cin >> k >> n;
	ll stoneocean = 0;
	Loop(i,0,n)
	{
		char c1,c2; ll a1,a2;
		cin >> c1 >> a1;
		cin >> c2 >> a2;
		if(c1==c2)
		{
			stoneocean += abs(a1-a2);
			--i; --n;
		}
		else
		{
			a[i] = {a1,a2};
			stoneocean += 1;
		}
	}
	sort(a,a+n,[](pll& x, pll& y){return x.F+x.S < y.F+y.S;});
	cout << stoneocean+(k==2?bin2():bin1(0,n)) << '\n';
}

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