#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=1e5+100,M=60;
vector <int> g[N];
map <pii,int> val;
int w[N*32];
pii nod[N*32];
int par[N*32];
int sz[N*32];
ll dp[N*32];
int n;
ll ma=(ll)1e15;
void dfssz(ll v){
sz[v]=w[v];
for (auto u : g[v]){
dfssz(u);
sz[v]+=sz[u];
}
}
void dfsdp(ll v){
for (auto u : g[v]){
dfsdp(u);
dp[v]+=dp[u];
ll e=nod[u].F-nod[v].F+nod[u].S-nod[v].S;
dp[v]+=(ll)sz[u]*e;
}
// cout << v << " " << sz[v] << endl;
}
void dfs(ll v){
ma=min(ma,dp[v]);
for (auto u : g[v]){
ll e=nod[u].F-nod[v].F+nod[u].S-nod[v].S;
dp[u]=(ll)dp[v]+(ll)e*(ll)n-(ll)2*(ll)e*(ll)sz[u];
dfs(u);
}
}
int32_t main(){
sync;
scanf("%d",&n);
// cin >> n;
vector <pii> a;
for (int i=0;i<n;i++){
int r,s;
scanf("%d %d",&r,&s);
//cin >> r >> s;
int f=r,h=s;
int x=0,y=0;
for (int j=M/2;j>-1;j--){
int z=x,t=y;
if ((r-x)>=(1<<j)){
x+=(1<<j);
a.pb({x,y});
}
if ((s-y)>=(1<<j)){
y+=(1<<j);
a.pb({x,y});
}
}
//cout << 1 << endl;
val[{r,s}]++;
}
a.pb({0,0});
sort(a.begin(),a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
for (int i=0;i<a.size();i++){
nod[i]=a[i];
}
for (int i=1;i<a.size();i++){
if (a[i].F==a[i-1].F && ((a[i].F)&(a[i].S-1))==0 && a[i].S!=0){
par[i]=i-1;
}
}
vector <pair <pii,int> > b;
for (int i=0;i<a.size();i++){
swap(a[i].F,a[i].S);
b.pb({a[i],i});
swap(a[i].F,a[i].S);
}
sort(b.begin(),b.end());
for (int i=1;i<b.size();i++){
pii d=b[i].F,e=b[i-1].F;
swap(d.F,d.S);
swap(e.F,e.S);
if (b[i].F.F==b[i-1].F.F && ((d.F-1)&(d.S))==0 && d.F!=0){
par[b[i].S]=b[i-1].S;
// cout << b[i].F.F << " " << b[i].F.S << endl;
// cout << nod[par[mp[{2,1}]]].F << " argers " << nod[par[mp[{2,1}]]].S << endl;
}
}
for (int i=1;i<a.size();i++){
g[par[i]].pb(i);
}
for (int i=0;i<a.size();i++){
w[i]=val[a[i]];
}
dfssz(0);
dfsdp(0);
dfs(0);
// cout << dp[1] << endl;
printf("%lld",ma);
// cout << ans-(1<<28);
}
/*
9
28 0
25 4
20 9
20 0
18 13
16 12
16 5
4 9
10 16
*/
Compilation message
cvenk.cpp: In function 'int32_t main()':
cvenk.cpp:60:17: warning: unused variable 'z' [-Wunused-variable]
int z=x,t=y;
^
cvenk.cpp:60:21: warning: unused variable 't' [-Wunused-variable]
int z=x,t=y;
^
cvenk.cpp:57:13: warning: unused variable 'f' [-Wunused-variable]
int f=r,h=s;
^
cvenk.cpp:57:17: warning: unused variable 'h' [-Wunused-variable]
int f=r,h=s;
^
cvenk.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<a.size();i++){
~^~~~~~~~~
cvenk.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1;i<a.size();i++){
~^~~~~~~~~
cvenk.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<a.size();i++){
~^~~~~~~~~
cvenk.cpp:91:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1;i<b.size();i++){
~^~~~~~~~~
cvenk.cpp:101:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1;i<a.size();i++){
~^~~~~~~~~
cvenk.cpp:104:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<a.size();i++){
~^~~~~~~~~
cvenk.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
cvenk.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&r,&s);
~~~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2816 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
2944 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2944 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2944 KB |
Output is correct |
| 4 |
Correct |
7 ms |
2944 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
114 ms |
19496 KB |
Output is correct |
| 2 |
Correct |
109 ms |
19588 KB |
Output is correct |
| 3 |
Correct |
65 ms |
11120 KB |
Output is correct |
| 4 |
Correct |
60 ms |
11028 KB |
Output is correct |
| 5 |
Correct |
68 ms |
11156 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
684 ms |
242180 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
