Submission #1105808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105808		_rain_	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	144 ms	12576 KiB

bridge

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define name "main"
#define int long long
typedef pair<int,int> ii;
#define fi first 
#define se second

const int N=(int)1e5;
bool print=false;
vector<ii>sett;
vector<ll>nen;
int n,k,cnt=0;
ll f[N+2];
bool used[N*2+2];

bool cmp(ii a,ii b){
	return a.fi+a.se<b.fi+b.se;
}
class BIT{
public:
	vector<ll>tot;
	vector<int> cnt,one;
	int n;
	void init(int _n){
		n=_n;
		tot.assign(_n+2,0);
		cnt.assign(_n+2,0);
		one.assign(_n+2,0);
		return;
	}
	void upd_tot(int id,int val){
		for(;id<=n;id+=(id&(-id)))
			tot[id]+=val;
		return;
	}
	void upd_cnt(int id,int val){
		for(;id<=n;id+=(id&(-id)))
			cnt[id]+=val;
		return;
	}
	void upd_one(int id,int val){
		for(;id<=n;id+=(id&(-id)))
			one[id]+=val;
	}
	int Get_tot(int id){
		ll sum=0;
		for(;id;id-=(id&(-id)))
			sum+=tot[id];
		return sum;
	}
	ll Get_cnt(int id){
		ll sum=0;
		for(;id;id-=(id&(-id)))
			sum+=cnt[id];

		return sum;
	}
	ll Get_one(int id){
		ll sum=0;
		for(;id;id-=(id&(-id)))
			sum+=one[id];
		return sum;
	}
	ll sum_range(int t,int l,int r){
		if (t==1){
			return Get_tot(r)-Get_tot(l-1);
		}
		if (t==2){
			return Get_cnt(r)-Get_cnt(l-1);
		}
		if (t==3){
			return Get_one(r)-Get_one(l-1);	
		}
	}
};	
BIT tree;

ll F(int i){
	int l=1,r=nen.size(),p=1;
	while(l<=r){
		int m=(l+r)>>1;
		if (tree.sum_range(2,1,m)<=(cnt+1)/2){
			l=m+1,p=m;
		}
		else r=m-1;
	}
	return nen[p]*tree.sum_range(2,1,p)-tree.sum_range(1,1,p)+tree.sum_range(1,p+1,nen.size())-nen[p]*tree.sum_range(2,p+1,nen.size())+(ll)i;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>k>>n;
	ll ans=0;
	nen.push_back(-1);
	for (int i=1;i<=n;++i){
		char c1,c2; int a,b;
		cin>>c1>>a>>c2>>b;
		if (c1==c2) ans+=abs(a-b);
		else {
			nen.push_back(a);
			nen.push_back(b);
			sett.push_back({a,b});
		}
	}
	sort(nen.begin(),nen.end()); nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	sort(sett.begin(),sett.end(),cmp);
	tree.init(nen.size());
	for (int i=1;i<=sett.size();++i){
		int a=sett[i-1].fi,b=sett[i-1].se;
		a=upper_bound(nen.begin(),nen.end(),a)-nen.begin();
		b=upper_bound(nen.begin(),nen.end(),b)-nen.begin();
		tree.upd_cnt(a,1),tree.upd_cnt(b,1);
		tree.upd_tot(a,nen[a-1]),tree.upd_tot(b,nen[b-1]);
		cnt+=2;
		f[i]=F(i);
	}
	if (k==1) ans=ans+f[sett.size()];
	else{
		tree.init(nen.size());
		cnt=0;
		ll add=(ll)1e18;
		for (int i=sett.size();i>=1;--i){
			int a=sett[i-1].fi,b=sett[i-1].se;
			a=upper_bound(nen.begin(),nen.end(),a)-nen.begin();
			b=upper_bound(nen.begin(),nen.end(),b)-nen.begin();
			tree.upd_cnt(a,1),tree.upd_cnt(b,1);
			tree.upd_tot(a,nen[a-1]),tree.upd_tot(b,nen[b-1]);
			cnt+=2;
			add=min(add,F(sett.size()-i+1)+f[i-1]);
		}
		ans=min(ans+f[sett.size()],ans+add);
	}
	cout<<ans;
	exit(0);
}

Compilation message (stderr)

bridge.cpp: In function 'int32_t main()':
bridge.cpp:112:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for (int i=1;i<=sett.size();++i){
      |               ~^~~~~~~~~~~~~
bridge.cpp: In member function 'll BIT::sum_range(long long int, long long int, long long int)':
bridge.cpp:77:2: warning: control reaches end of non-void function [-Wreturn-type]
   77 |  }
      |  ^

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