#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=3e5+100,M=60;
vector <int> g[N];
map <pii,int> mp;
ll w[N*M];
pii nod[N*M];
ll par[N*M];
ll sz[N*M];
ll dp[N*M];
ll n;
ll ma=(ll)1e15;
ll dfssz(ll v){
sz[v]=w[v];
for (auto u : g[v]){
dfssz(u);
sz[v]+=sz[u];
}
}
ll 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]+=sz[u]*e;
}
}
ll 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]=dp[v]+e*n-2*e*sz[u];
dfs(u);
}
}
int32_t main(){
cin >> n;
vector <pii> a;
ll cnt=2;
mp[{0,0}]=1;
nod[1]={0,0};
ll ans=0;
for (int i=0;i<n;i++){
ll r,s;
cin >> r >> s;
ans+=r+s;
ll f=r,h=s;
ll x=0,y=0;
for (int j=M/2;j>-1;j--){
ll z=x,t=y;
if ((r-x)>=(1<<j)){
x+=(1<<j);
}
if (mp[{x,y}]==0){
nod[cnt]={x,y};
par[cnt]=mp[{z,t}];
mp[{x,y}]=cnt++;
}
a.pb({x,y});
if ((s-y)>=(1<<j)){
y+=(1<<j);
}
a.pb({x,y});
if (mp[{x,y}]==0){
nod[cnt]={x,y};
// cout << x << " " << y << endl;
par[cnt]=mp[{z,t}];
mp[{x,y}]=cnt++;
}
}
w[mp[{r,s}]]++;
}
a.pb({0,0});
sort(a.begin(),a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
for (int i=1;i<a.size();i++){
if (a[i].F==a[i-1].F && nod[par[mp[a[i]]]].S<=nod[mp[a[i-1]]].S && nod[par[mp[a[i]]]].F==nod[mp[a[i-1]]].F){
par[mp[a[i]]]=mp[a[i-1]];
}
}
// cout << nod[par[mp[{2,1}]]].F << " argers " << nod[par[mp[{2,1}]]].S << endl;
vector <pii> b;
for (int i=0;i<a.size();i++){
swap(a[i].F,a[i].S);
b.pb(a[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],e=b[i-1];
swap(d.F,d.S);
swap(e.F,e.S);
if (b[i].F==b[i-1].F && nod[par[mp[d]]].F<=nod[mp[e]].F && nod[par[mp[d]]].S==nod[mp[e]].S){
par[mp[d]]=mp[e];
// 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[mp[a[i]]]].pb(mp[a[i]]);
// cout << par[mp[a[i]]] << " " << mp[a[i]] << " " << nod[mp[a[i]]].F << " " << nod[mp[a[i]]].S << " " << nod[par[mp[a[i]]]].F << " " << nod[par[mp[a[i]]]].S << endl;
}
dfssz(mp[{0,0}]);
dfsdp(mp[{0,0}]);
dfs(mp[{0,0}]);
cout << ma << endl;
// 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 'll dfssz(ll)':
cvenk.cpp:30:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
cvenk.cpp: In function 'll dfsdp(ll)':
cvenk.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
cvenk.cpp: In function 'll dfs(ll)':
cvenk.cpp:46:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
cvenk.cpp: In function 'int32_t main()':
cvenk.cpp:58:12: warning: unused variable 'f' [-Wunused-variable]
ll f=r,h=s;
^
cvenk.cpp:58:16: warning: unused variable 'h' [-Wunused-variable]
ll f=r,h=s;
^
cvenk.cpp:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1;i<a.size();i++){
~^~~~~~~~~
cvenk.cpp:94:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<a.size();i++){
~^~~~~~~~~
cvenk.cpp:100:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1;i<b.size();i++){
~^~~~~~~~~
cvenk.cpp:109:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1;i<a.size();i++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
10 ms |
7424 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 4 |
Correct |
9 ms |
7424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
7808 KB |
Output is correct |
| 2 |
Correct |
10 ms |
7808 KB |
Output is correct |
| 3 |
Correct |
11 ms |
7808 KB |
Output is correct |
| 4 |
Correct |
12 ms |
7808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
750 ms |
139336 KB |
Output is correct |
| 2 |
Correct |
718 ms |
139476 KB |
Output is correct |
| 3 |
Correct |
493 ms |
138964 KB |
Output is correct |
| 4 |
Correct |
539 ms |
138964 KB |
Output is correct |
| 5 |
Correct |
572 ms |
138964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3089 ms |
275304 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
