oj.uz

Submission #197738

# Submission time Handle Problem Language Result Execution time Memory
197738 2020-01-22T16:33:09 Z dolphingarlic ČVENK (COI15_cvenk) C++14
100 / 100
 410 ms 92872 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 26932 KB Output is correct
2 Correct 119 ms 26872 KB Output is correct
3 Correct 97 ms 18124 KB Output is correct
4 Correct 94 ms 16892 KB Output is correct
5 Correct 99 ms 18360 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 92872 KB Output is correct
2 Correct 410 ms 92824 KB Output is correct
3 Correct 286 ms 88952 KB Output is correct
4 Correct 272 ms 78940 KB Output is correct
5 Correct 276 ms 76336 KB Output is correct