Submission #410269

#	Time	Username	Problem	Language	Result	Execution time	Memory
410269		CSQ31	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2077 ms	16444 KiB

bridge

#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
int main()
{
	owo
	int k,n;
	cin>>k>>n;
	vector<int>s,t;
	ll ans = 0;
	for(int i=0;i<n;i++){
		char a,c;
		int b,d;
		cin>>a>>b>>c>>d;
		if(a == c){ans+=abs(d-b);continue;}
		s.pb(b);
		t.pb(d);
	}
	if(k == 1){
		vector<int>p;
		for(int x:s)p.pb(x);
		for(int x:t)p.pb(x);
		if(!p.empty()){
		sort(all(p));
		   int mid = p[sz(p)/2];
		   for(int i=0;i<sz(p)/2;i++)ans+=mid-p[i];
		   for(int i=sz(p)/2;i<sz(p);i++)ans+=p[i]-mid;
	    }
	    cout<<ans+sz(p)/2;
	}
	else{
		n = sz(s);
		ll add  =0;
		if(n){
		vector<ll>pref(n),suff(n);
		multiset<int,greater<int>>lf;
		multiset<int>rg;
		ll slf = 0,srg = 0;
		vector<int>id(n);
		for(int i=0;i<n;i++)id[i] = i;
		sort(all(id),[=](int x,int y){return s[y]+t[y] > s[x]+t[x];});
		for(int i=0;i<n;i++){
			int a = s[id[i]];
			int b = t[id[i]];
			//cout<<a<<" "<<b<<'\n';
			lf.insert(a);
			lf.insert(b);
			slf+=a;
			slf+=b;
			while(sz(lf)-sz(rg)>1){
				rg.insert(*lf.begin());
				srg+=*lf.begin();
				slf-=*lf.begin();
				lf.erase(lf.begin());
			}
			while(!lf.empty() && !rg.empty() && *lf.begin() > *rg.begin()){
				int ta = *lf.begin();
				int tb = *rg.begin();
				slf+=tb-ta;
				srg+=ta-tb;
				lf.erase(lf.begin());
				rg.erase(rg.begin());
				lf.insert(tb);
				rg.insert(ta);
				
			}
			ll mid = *lf.begin();
			pref[i] = sz(lf)*mid - slf + srg - sz(rg)*mid;
		}
		
		slf = srg = 0;
		lf.clear();
		rg.clear();
		for(int i=n-1;i>=0;i--){
			int a = s[id[i]];
			int b = t[id[i]];
			//cout<<a<<" "<<b<<'\n';
			lf.insert(a);
			lf.insert(b);
			slf+=a;
			slf+=b;
			while(sz(lf)-1 > sz(rg)){
				rg.insert(*lf.begin());
				srg+=*lf.begin();
				slf-=*lf.begin();
				lf.erase(lf.begin());
			}
			while(!lf.empty() && !rg.empty() && *lf.begin() > *rg.begin()){
				int ta = *lf.begin();
				int tb = *rg.begin();
				slf+=tb-ta;
				srg+=ta-tb;
				lf.erase(lf.begin());
				rg.erase(rg.begin());
				lf.insert(tb);
				rg.insert(ta);
				
			}
			ll mid = *lf.begin();
			suff[i] = sz(lf)*mid - slf + srg - sz(rg)*mid;
		}
		add = min(pref[n-1],suff[0]);
		for(int i=0;i<n-1;i++)add = min(add,pref[i]+suff[i+1]);
	}
		cout<<ans+add+n<<'\n';
	}
}
/*
1 5
B0A4
B1B3
A5B7
B2A6
B1A7
2 5
B0A4
B1B3
A5B7
B2A6
B1A7
*/

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