제출 #477347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
477347		ymm	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	150 ms	9036 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;

vector<ll> stb;
ll cntl[2*N], cntr[2*N];

#ifndef EVAL
void dbg(){cout << "!\n";}
template<class T, class... U> void dbg(T x, U... y){cout << x << ' '; dbg(y...);}
#else
template<class... T> void dbg(T... x){}
#endif

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};
			stb.push_back(a1);
			stb.push_back(a2);
			stoneocean += 1;
		}
	}
	if(n == 0) return cout << stoneocean << '\n', 0;
	sort(stb.begin(),stb.end());
	stb.resize(unique(stb.begin(),stb.end())-stb.begin());
	Loop(i,0,n)
		cntr[lower_bound(stb.begin(),stb.end(),a[i].F)-stb.begin()]++,
		cntr[lower_bound(stb.begin(),stb.end(),a[i].S)-stb.begin()]++;
	sort(a,a+n,[](pll& x, pll& y){return x.F+x.S < y.F+y.S;});
	int p1 = 0, p2 = 0;
	ll c1 = 0, c2 = 2*n - 2*cntr[0];
	ll suml = 0, sumr = -2*n*stb[0]; Loop(i,0,n) sumr += a[i].F+a[i].S;
	while(c2 > 0) {
		sumr -= c2*(stb[p2+1]-stb[p2]);
		++p2;
		c2 -= 2*cntr[p2];
	}
	if(k==1) return cout << stoneocean+sumr << '\n', 0;
	auto mov = [&](int i) -> void{
		sumr -= abs(a[i].F-stb[p2]);
		sumr -= abs(a[i].S-stb[p2]);
		suml += abs(a[i].F-stb[p1]);
		suml += abs(a[i].S-stb[p1]);
		c2 -= a[i].F <= stb[p2]? -1: 1;
		c2 -= a[i].S <= stb[p2]? -1: 1;
		c1 += a[i].F <= stb[p1]? -1: 1;
		c1 += a[i].S <= stb[p1]? -1: 1;
		cntr[lower_bound(stb.begin(),stb.end(),a[i].F)-stb.begin()]--;
		cntl[lower_bound(stb.begin(),stb.end(),a[i].F)-stb.begin()]++;
		cntr[lower_bound(stb.begin(),stb.end(),a[i].S)-stb.begin()]--;
		cntl[lower_bound(stb.begin(),stb.end(),a[i].S)-stb.begin()]++;
	};
	ll ans = suml+sumr;
	Loop(i,0,n)
	{
		mov(i);
		while(c2 > 0) {
			sumr -= c2*(stb[p2+1]-stb[p2]);
			++p2;
			c2 -= 2*cntr[p2];
		}
		while(c1 > 0) {
			suml -= c1*(stb[p1+1]-stb[p1]);
			++p1;
			c1 -= 2*cntl[p1];
		}
		ans = min(ans, suml+sumr);
	}
	cout << stoneocean+ans << '\n';
}

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