Submission #108085

#	Time	Username	Problem	Language	Result	Execution time	Memory
108085		autumn_eel	Palembang Bridges (APIO15_bridge)	C++14	31 / 100	2061 ms	5544 KiB

bridge

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define int long long

map<int,int>bit[2];
void add(int t,int k,int x){
	k++;
	while(k<=1e9+1){
		bit[t][k]+=x;
		k+=k&-k;
	}
}
int query(int t,int k){
	k++;
	int res=0;
	while(k){
		res+=bit[t][k];
		k-=k&-k;
	}
	return res;
}

char p[200000][2],q[200000][2];
int s[200000],t[200000];
signed main(){
	int K,n;cin>>K>>n;
	if(K==1){
		vector<int>v;
		ll sum=0;
		rep(i,n){
			scanf("%s%lld%s%lld",p[i],&s[i],q[i],&t[i]);
			if(p[i][0]==q[i][0]){
				sum+=abs(s[i]-t[i]);
				continue;
			}
			sum++;
			v.push_back(s[i]);
			v.push_back(t[i]);
		}
		sort(v.begin(),v.end());
		if(!v.empty()){
			int md=v[v.size()/2];
			for(int i:v)sum+=abs(i-md);
		}
		cout<<sum<<endl;
		return 0;
	}
	ll sum=0;
	vector<P>v;
	vector<int>xs;
	rep(i,n){
		scanf("%s%lld%s%lld",p[i],&s[i],q[i],&t[i]);
		if(p[i][0]==q[i][0]){
			sum+=abs(s[i]-t[i]);
			continue;
		}
		sum++;
		v.push_back(P(min(s[i],t[i]),max(s[i],t[i])));
		xs.push_back(s[i]);
		xs.push_back(t[i]);
	}
	if(v.empty()){
		cout<<sum<<endl;
		return 0;
	}
	sort(xs.begin(),xs.end());
	xs.erase(unique(xs.begin(),xs.end()),xs.end());
	ll Min=LLONG_MAX;
	for(int i:xs){
		bit[0].clear();
		bit[1].clear();
		ll cnt=0;
		for(auto p:v){
			if(p.first<=i){
				cnt+=abs(p.first-i)+abs(p.second-i);
				continue;
			}
			add(1,0,abs(p.first-i)+abs(p.second-i));// a
			add(1,i,-abs(p.first-i)-abs(p.second-i));// a'
			add(0,i,-2);// b
			add(1,i,abs(p.first-i)+abs(p.second-i)-(-2*i));// c
			add(0,p.first,2);// b'
			add(1,p.first,-abs(p.first-i)-abs(p.second-i)+(-2*i));// c'
			add(1,p.first,p.second-p.first);// d
			add(1,p.second,p.first-p.second);// d'
			add(0,p.second,2);//e
			add(1,p.second,(p.second-p.first)-2*p.second);//f
			int ok=p.second,ng=1e9+2;
			while(ng-ok>1){
				int t=(ok+ng)/2;
				if(abs(t-p.first)+abs(t-p.second)<=abs(p.first-i)+abs(p.second-i))ok=t;
				else ng=t;
			}
			add(0,ng,-2);//e'
			add(1,ng,-((p.second-p.first)-2*p.second));//f'
			add(1,ng,abs(p.first-i)+abs(p.second-i));//g
			//~ cout<<"---- "<<i<<' '<<p.first<<' '<<p.second<<" ----"<<endl;
			//~ for(int j=0;j<=10;j++){
				//~ cout<<j<<' '<<query(0,j)*j+query(1,j)<<endl;
			//~ }
		}
		ll d=LLONG_MAX;
		for(int j:xs){
			d=min(d,query(0,j)*(ll)j+query(1,j));
		}
		Min=min(Min,cnt+d);
	}
	cout<<sum+Min<<endl;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s%lld%s%lld",p[i],&s[i],q[i],&t[i]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%lld%s%lld",p[i],&s[i],q[i],&t[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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