Submission #108078

#	Time	Username	Problem	Language	Result	Execution time	Memory
108078		autumn_eel	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	4 ms	640 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;

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];
int main(){
	int K,n;cin>>K>>n;
	if(K==1){
		vector<int>v;
		ll sum=0;
		rep(i,n){
			scanf("%s%d%s%d",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());
		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%d%s%d",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,2*p.second-(p.second-p.first));//f
		}
		ll d=LLONG_MAX;
		for(auto j:xs){
			d=min(d,query(0,j)*(ll)j+query(1,j));
		}
		Min=min(Min,cnt+d);
	}
	/*
	ll Min=LLONG_MAX;
	rep(i,xs.size())rep(j,xs.size()){
		ll cnt=0;
		rep(k,v.size()){
			cnt+=min(abs(xs[i]-v[k].first)+abs(xs[i]-v[k].second),
					abs(xs[j]-v[k].first)+abs(xs[j]-v[k].second));
		}
		Min=min(Min,cnt);
	}*/
	cout<<sum+Min<<endl;
}

Compilation message (stderr)

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

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