Submission #487891

#	Time	Username	Problem	Language	Result	Execution time	Memory
487891		MilosMilutinovic	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	230 ms	22876 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
const ll mod2=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=101000;
int k,n,m,s[N],t[N],a[N],b[N],p[N];
char ss[N],tt[N];
ll pf[N],sf[N];

struct ds{
	int med;
	ll sm;
	ds() { sm=0; }
	multiset<int> L,R;
	void add(int x,int y) {
		if (x>y) swap(x,y);
		if (SZ(L)==0) {
			sm=y-x;
			L.insert(x);
			R.insert(y);
			med=x;
			return;
		}
		(x<=med?L:R).insert(x);
		(y<=med?L:R).insert(y);
		while (SZ(L)>SZ(R)) {
			R.insert(*prev(L.end()));
			L.erase(prev(L.end()));
		}
		while (SZ(L)<SZ(R)) {
			L.insert(*R.begin());
			R.erase(R.begin());
		}
		int nm=*prev(L.end());
		sm+=abs(nm-x)+abs(nm-y);
		if (med>nm) sm+=abs(med-nm)*2;
		med=nm;
	}
};

int main() {
	scanf("%d%d",&k,&n);
	rep(i,1,n+1) scanf("\n%c %d %c %d",ss+i,s+i,tt+i,t+i);
	ll ans=1e18,same=0;
	rep(i,1,n+1) {
		if (ss[i]==tt[i]) {
			same+=abs(s[i]-t[i]);
		}
		else a[++m]=s[i],b[m]=t[i];
	}
	if (m==0) {
		printf("%lld\n",same);
		return 0;
	}
	rep(i,1,m+1) p[i]=i;
	sort(p+1,p+1+m,[&](int i,int j) {
		return a[i]+b[i]<a[j]+b[j];
	});
	ds pref;
	pref.sm=0;
	rep(i,1,m+1) {
		pref.add(a[p[i]],b[p[i]]);
		pf[i]=pref.sm;
	}
	ds suff;
	suff.sm=0;
	per(i,1,m+1) {
		suff.add(a[p[i]],b[p[i]]);
		sf[i]=suff.sm;
	}
	/*rep(i,1,m+1) {
		printf("%lld %lld\n",pf[i],sf[i]);
	}*/
	rep(i,1,m+1) ans=min(ans,pf[i]+sf[i+1]);
	if (k==2) printf("%lld",ans+same+m);
	else printf("%lld\n",pf[m]+same+m);
}

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

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

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d%d",&k,&n);
      |  ~~~~~^~~~~~~~~~~~~~
bridge.cpp:61:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  rep(i,1,n+1) scanf("\n%c %d %c %d",ss+i,s+i,tt+i,t+i);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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