이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n"
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
array<int,2> lca(array<int,2> a,array<int,2> b){
vector<array<int,2>> par_a;
vector<array<int,2>> par_b;
par_a.pb(a);
par_b.pb(b);
while(a[0]>0 && a[1]>0 ){
int x = a[0]&-a[0];
int y = a[1]&-a[1];
if(x>y){
a[1]-=y;
par_a.pb(a);
}
else{
a[0]-=x;
par_a.pb(a);
}
}
while(a[0]>0){
a[0]-=a[0]&-a[0];
par_a.pb(a);
}
while(a[1]>0){
a[1]-=a[1]&-a[1];
par_a.pb(a);
}
while(b[0]>0 && b[1]>0 ){
int x = b[0]&-b[0];
int y = b[1]&-b[1];
if(x>y){
b[1]-=y;
par_b.pb(b);
}
else{
b[0]-=x;
par_b.pb(b);
}
}
while(b[0]>0){
b[0]-=b[0]&-b[0];
par_b.pb(b);
}
while(b[1]>0){
b[1]-=b[1]&-b[1];
par_b.pb(b);
}
map<int,int> mpr;
map<int,int> mpc;
for(int i=0;i<sz(par_b);i++){
auto x = par_b[i];
if(!mpr.count(x[0])) mpr[x[0]]= i;
if(!mpc.count(x[1])) mpc[x[1]]= i;
}
array<int,2> res={0,0};
for(int i=0;i<sz(par_a);i++){
auto x = par_a[i];
if(mpr.count(x[0])){
array<int,2> cur = {x[0],min(x[1],par_b[mpr[x[0]]][1])};
res=max(res,cur);
break;
}
}
for(int i=0;i<sz(par_a);i++){
auto x = par_a[i];
if(mpc.count(x[1])){
array<int,2> cur = {min(x[0],par_b[mpc[x[1]]][0]),x[1]};
res=max(res,cur);
break;
}
}
return res;
}
void solve(){
int n;
cin >> n;
vector<array<int,2>> v;
for(int i=0;i<n;i++){
int a,b;
cin >> a >> b;
v.pb({a,b});
}
array<int,2> xd = lca(v[0],v[1]);
int ans=0;
ans+=v[0][0]-xd[0]+v[0][1]-xd[1];
ans+=v[1][0]-xd[0]+v[1][1]-xd[1];
cout << ans << endl;
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int t=1;//cin >> t;
while(t--) solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |