Submission #42577

#	Time	Username	Problem	Language	Result	Execution time	Memory
42577		fefe	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	2 ms	780 KiB

bridge

#include<bits/stdc++.h>
#define MAX_N 100005
#define inf (1LL<<60)
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pil;
struct node{
	LL cnt,sum;
	node *l,*r;
	node(LL cnt,LL sum,node *l,node *r):cnt(cnt),sum(sum),l(l),r(r){}
	node *update(LL idx,LL p,LL val,LL x){
		if(idx<0)	return new node(cnt+x,sum+x*val,NULL,NULL);
		if(p>>idx&(1LL))	return new node(cnt+x,sum+x*val,l,r->update(idx-1,p,val,x));
		return new node(cnt+x,sum+x*val,l->update(idx-1,p,val,x),r);
	}
}*R1,*R2;
LL n,k,m;
LL ans,aa;
vector<LL> X;
pil arr[MAX_N];
pil serch(LL idx,node *x,LL cnt,LL p){
	if(idx<0)	return {X[p],X[p]*cnt};
	if(x->l->cnt<cnt){
		pil q=serch(idx-1,x->r,cnt-x->l->cnt,(p|(1LL<<idx)));
		q.se+=x->l->sum;
		return q;
	}
	return serch(idx-1,x->l,cnt,p);
}
LL read(node *RX){
	pil p=serch(19,RX,RX->cnt/2,0);
	return (RX->cnt/2)*p.fi-p.se+(RX->sum-p.se)-(RX->cnt-RX->cnt/2)*p.fi;
}
int main(){
	LL i,x;
	char a[5],b[5];
	scanf("%lld %lld",&k,&n);
	for(i=1;i<=n;i++){
		scanf("%s %lld %s %lld",a,&arr[m].fi,b,&arr[m].se);
		if(a[0]==b[0]){
			aa+=abs(arr[m].fi-arr[m].se);
			continue;
		}
		X.pb(arr[m].fi);X.pb(arr[m].se);
		m++;
		aa++;
	}
	sort(X.begin(),X.end());X.erase(unique(X.begin(),X.end()),X.end());
	sort(arr,arr+m,[&](const pil x,const pil y){
		return x.fi+x.se<y.fi+y.se;
	});
	R1=new node(0,0,NULL,NULL);R1->l=R1->r=R1;
	R2=new node(0,0,NULL,NULL);R2->l=R2->r=R2;
	for(i=0;i<m;i++){
		R2=R2->update(19,(lower_bound(X.begin(),X.end(),arr[i].fi)-X.begin()),arr[i].fi,1);
		R2=R2->update(19,(lower_bound(X.begin(),X.end(),arr[i].se)-X.begin()),arr[i].se,1);
	}
	ans=read(R2);
	if(k==1)	return !printf("%lld\n",aa+ans);
	for(i=0;i<m;i++){
		R1=R1->update(19,(lower_bound(X.begin(),X.end(),arr[i].fi)-X.begin()),arr[i].fi,1);
		R1=R1->update(19,(lower_bound(X.begin(),X.end(),arr[i].se)-X.begin()),arr[i].se,1);
		R2=R2->update(19,(lower_bound(X.begin(),X.end(),arr[i].fi)-X.begin()),arr[i].fi,-1);
		R2=R2->update(19,(lower_bound(X.begin(),X.end(),arr[i].se)-X.begin()),arr[i].se,-1);
		x=read(R1)+read(R2);
		ans=min(ans,x);
	}
	printf("%lld\n",aa+ans);
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:40:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&k,&n);
                          ^
bridge.cpp:42:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s %lld %s %lld",a,&arr[m].fi,b,&arr[m].se);
                                                     ^

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