#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
bool cnt[200005][2];
int main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll ans = 0;
int n;cin>>n;
map<int,int> mp[2];
for(int i=0;i<2*n;i++){
int x,y;cin>>x>>y;
if(y>=2){
if(x<1){
mp[1][1]++;
cnt[1][1]=1;
ans+=abs(x-1)+abs(y-2);
}else if(x>n){
mp[n][1]++;
cnt[n][1]=1;
ans+=abs(x-n)+abs(y-2);
}else{
mp[1][x]++;
cnt[x][1]=1;
ans+=abs(y-2);
}
}else{
if(x<1) {
mp[0][1]++;
cnt[1][0]=1;
ans+=abs(x-1)+abs(y-1);
}else if(x>n){
mp[0][n]++;
cnt[n][0]=1;
ans+=abs(x-n)+abs(y-1);
}else{
mp[0][x]++;
cnt[x][0]=1;
ans+=abs(y-1);
}
}
}
for(auto i : mp[0]){
mp[0][i.first]--;
if(mp[0][i.first]==0) mp[0].erase(i.first);
}
for(auto i : mp[1]){
mp[1][i.first]--;
if(mp[1][i.first]==0) mp[1].erase(i.first);
}
for(int j=0;j<=1;j++){
for(int i=1;i<=n;i++){
if(cnt[i][j]) continue;
auto low = mp[j].lower_bound(i);
pair<int,int> result = {1e9,0};
if(low==mp[j].end()){
if(mp[j].size()) result = min(result,make_pair(abs(mp[j].rbegin()->first-i),mp[j].rbegin()->first));
}else if(low==mp[j].begin()){
result = min(result,make_pair(abs(low->first-i),low->first));
}else{
auto pv = prev(low);
result = min(result,make_pair(abs(low->first-i),low->first));
result = min(result,make_pair(abs(pv->first-i),pv->first));
}
auto low2 = mp[j^1].lower_bound(i);
pair<int,int> result2 = {1e9,0};
if(low2==mp[j^1].end()){
if(mp[j^1].size()) result2 = min(result2,make_pair(abs(mp[j^1].rbegin()->first-i)+1,mp[j^1].rbegin()->first));
}else if(low2==mp[j^1].begin()){
result2 = min(result2,make_pair(abs(low2->first-i)+1,low2->first));
}else{
auto pv = prev(low2);
result2 = min(result2,make_pair(abs(low2->first-i)+1,low2->first));
result2 = min(result2,make_pair(abs(pv->first-i)+1,pv->first));
}
if(result.first<result2.first){
ans+=result.first;
mp[j][result.second]--;
// cout<<j<<"\n";
if(mp[j][result.second]==0) mp[j].erase(result.second);
}else{
ans+=result2.first;
mp[j^1][result2.second]--;
// cout<<(j^1)<<"\n";
if(mp[j^1][result2.second]==0) mp[j^1].erase(result2.second);
}
//cout<<i<<" "<<j<<" "<<ans<<"\n";
}
}
cout<<ans<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
