Submission #259655

#	Time	Username	Problem	Language	Result	Execution time	Memory
259655		kshitij_sodani	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	1419 ms	47416 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
llo k,n;
map<llo,llo> ind;
llo ind2[200001];
llo pre[100001];
llo pre2[100001];
llo tree3[300001];
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define ord tree<pair<llo,llo>,null_type,less<pair<llo,llo>>,rb_tree_tag,tree_order_statistics_node_update>

void u(llo i,llo j){
	while(i<300001){
		tree3[i]+=j;
		i+=(i&-i);
	}
}
llo s(llo i){
	llo su=0;
	while(i>0){
		su+=tree3[i];
		i-=(i&-i);
	}
	return su;
}
llo tree2[300001];
void u2(llo i,llo j){
	while(i<300001){
		tree2[i]+=j;
		i+=(i&-i);
	}
}
llo s2(llo i){
	llo su=0;
	while(i>0){
		su+=tree2[i];
		i-=(i&-i);
	}
	return su;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>k>>n;
	set<llo> cur;
	vector<pair<llo,pair<llo,llo>>> ss;
	llo ans=0;
	llo nn=n;
	for(llo i=0;i<n;i++){
		char so,t;
		llo aa,bb;
		cin>>so>>aa>>t>>bb;
		if(so==t){
			ans+=abs(aa-bb);
			nn-=1;
			continue;
		}
		ans+=1;
		//cout<<so<<":"<<aa<<":"<<t<<":"<<bb<<endl;
		cur.insert(aa);
		cur.insert(bb);
		ss.pb({aa+bb,{aa,bb}});
	}
	if(nn==0){
		cout<<ans<<endl;
		return 0;
	}
	n=nn;
	llo ii=0;
	for(auto j:cur){
		ind[j]=ii;
		ind2[ii]=j;
		ii+=1;
	}

	sort(ss.begin(),ss.end());
	llo co=0;
	ord cur2;
	for(llo i=0;i<n;i++){
		co+=2;
		u(ind[ss[i].b.a]+1,ss[i].b.a);
		u(ind[ss[i].b.b]+1,ss[i].b.b);
		u2(ind[ss[i].b.a]+1,1);
		u2(ind[ss[i].b.b]+1,1);
		cur2.insert({ind[ss[i].b.a],i*2});
		cur2.insert({ind[ss[i].b.b],i*2+1});
		pair<llo,llo> y=*cur2.find_by_order(co/2-1);
	//	cout<<y.a<<":"<<y.b<<endl;
		llo ind3=y.a;
	//	cout<<y.a<<","<<y.b<<endl;
	//	cout<<ind2[ind3]<<endl;
		llo ss3=s2(ind3+1);
		llo ss2=s(ind3+1);
		llo cost=ss3*ind2[ind3]-ss2;
	//	cout<<cost<<endl;
	//	cout<<cost<<endl;
		llo co2=s(2*n+1)-s(ind3+1);
		llo co3=s2(2*n+1)-s2(ind3+1);
	//	cout<<co2<<"::"<<co3<<endl;
		cost+=co2-ind2[ind3]*co3;

		pre[i]=cost;
//		cout<<pre[i]<<"/"<<endl;
	//	cout<<ss[i].a<<":"<<ss[i].b.a<<":"<<ss[i].b.b<<endl;
	//	cout<<cost<<endl;
	}
//	cout<<endl;
	memset(tree3,0,sizeof(tree3));
	memset(tree2,0,sizeof(tree2));
	co=0;
	cur2.clear();
	for(llo i=n-1;i>=0;i--){
		co+=2;
		u(ind[ss[i].b.a]+1,ss[i].b.a);
		u(ind[ss[i].b.b]+1,ss[i].b.b);
		u2(ind[ss[i].b.a]+1,1);
		u2(ind[ss[i].b.b]+1,1);
		cur2.insert({ind[ss[i].b.a],i*2});
		cur2.insert({ind[ss[i].b.b],i*2+1});
		pair<llo,llo> y=*cur2.find_by_order(co/2-1);
	//	cout<<y.a<<":"<<y.b<<endl;
		llo ind3=y.a;
	//	cout<<y.a<<","<<y.b<<endl;
	//	cout<<ind2[ind3]<<endl;
		llo ss3=s2(ind3+1);
		llo ss2=s(ind3+1);
		llo cost=ss3*ind2[ind3]-ss2;
	//	cout<<cost<<endl;
	//	cout<<cost<<endl;
		llo co2=s(2*n+1)-s(ind3+1);
		llo co3=s2(2*n+1)-s2(ind3+1);
	//	cout<<co2<<"::"<<co3<<endl;
		cost+=co2-ind2[ind3]*co3;

		pre2[i]=cost;
	//	cout<<pre[i]<<"/"<<endl;
	//	cout<<ss[i].a<<":"<<ss[i].b.a<<":"<<ss[i].b.b<<endl;
	//	cout<<cost<<endl;
	}

	if(k==1){
		cout<<pre[n-1]+ans<<endl;
	}
	else{
		llo ans2=pre[n-1];
		

		for(llo i=0;i<n-1;i++){
			ans2=min(ans2,pre[i]+pre2[i+1]);
		}
	//	cout<<ans2<<endl;
		cout<<ans2+ans<<endl;
	}







	return 0;
}

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