Submission #533689

#	Time	Username	Problem	Language	Result	Execution time	Memory
533689		new_acc	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	103 ms	13128 KiB

bridge

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
struct st{
	int a,b,sr;
};
st t[N];
multiset<pair<int,int> > mu;
multiset<pair<int,int> >::iterator it;
ll summ,sumw;
int ilem,ilew,curr;
void add(int x,int ind){
	mu.insert({x,ind});
	if(x>=curr) ilew++,sumw+=(ll)x;
	else summ+=(ll)x,ilem++;
	if(ilew>ilem){
		ilew--,ilem++;
		summ+=(ll)curr;
		it++;
		curr=(*it).fi;
		sumw-=(ll)curr;
	}else{
		if(ilem-1>ilew){
			ilem--,ilew++;
			sumw+=(ll)curr;
			it--;
			curr=(*it).fi;
			summ-=(ll)curr;
		}
	}
}	
void solve(){
	int n,k;
	cin>>k>>n;
	ll res=0;
	int l=0;
	for(int i=1;i<=n;i++){
		char a,c;
		int b,d;
		cin>>a>>b>>c>>d;
		if(a==c) res+=(ll)abs(d-b);
		else{
			res++;
			st pom;
			pom.a=b,pom.b=d,pom.sr=(b+d);
			t[++l]=pom;
		}
	}
	n=l;
	sort(t+1,t+1+n,[](st a,st b){
		return a.sr<b.sr;
	});
	mu.insert({t[1].a,1});
	curr=t[1].a;
	it=mu.begin();
	add(t[1].b,2);
	if(k==1){
		for(int i=2;i<=n;i++){
			add(t[i].a,i*2-1);
			add(t[i].b,i*2);
		}
		cout<<(ll)curr*(ll)ilem-summ+sumw-(ll)curr*(ll)ilew+res<<"\n";
	}
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

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