Submission #197738

#	Time	Username	Problem	Language	Result	Execution time	Memory
197738		dolphingarlic	ČVENK (COI15_cvenk)	C++14	100 / 100	410 ms	92872 KiB

cvenk

#include<bits/stdc++.h>
using namespace std;typedef long long u;u td=0,s=LLONG_MAX,n;struct N{u x,y,l;N *c[2];N(u X=0,u Y=0):x(X),y(Y),l(0){c[0]=c[1]=NULL;}N* ist(N *ins,int z){l++;if(!c[z]){c[z]=ins;return ins;}if(ins->x<c[z]->x||ins->y<c[z]->y){ins->c[z]=c[z];ins->l+=c[z]->l;c[z]=ins;return ins;}if(ins->x>c[z]->x||ins->y>c[z]->y)return c[z]->ist(ins,z);return c[z];}};N *r=new N();void d(N *c){s=min(s,td);for(int i=0;i<2;i++){if(c->c[i]){u dx=c->x-c->c[i]->x+c->y-c->c[i]->y;td+=dx*(2*c->c[i]->l-n);d(c->c[i]);td-=dx*(2*c->c[i]->l-n);}}}pair<u,u> a[100000];bool cmp(pair<u,u> x,pair<u,u> y){return x.first+x.second>y.first+y.second;}int main(){cin>>n;for(int i=0;i<n;i++){cin>>a[i].first>>a[i].second;td+=a[i].first+a[i].second;}sort(a,a+n,cmp);for(int i=0;i<n;i++){N *c=r;u x=0,y=0;for(int j=29;~j;j--){if(a[i].first&(1<<j)){x|=(1<<j);c=c->ist(new N(x,y),0);}else if(a[i].second&(1<<j)){y|=(1<<j);c=c->ist(new N(x,y),1);}}c->l++;}d(r);cout<<s;}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40