#include <bits/stdc++.h>
using namespace std;
struct segmenttree{
vector<int> leftmost;
vector<int> array;
int sze;
segmenttree(int _sze, int arr[]):sze(_sze){
leftmost.resize(4*sze+5);
array.resize(sze);
for(int i=0; i<4*sze+5; i++){
leftmost[i]=sze;
}
for(int i=0; i<sze; i++){
array[i]=arr[i];
}
build(0, 0, sze-1);
}
void build(int segpos, int nodeleft, int noderight){
if(nodeleft!=noderight){
int nodemid = (nodeleft+noderight)/2;
build(2*segpos+1, nodeleft, nodemid);
build(2*segpos+2, nodemid+1, noderight);
leftmost[segpos]=min(leftmost[2*segpos+1], leftmost[2*segpos+2]);
}
else{
if(array[nodeleft]!=0){
leftmost[segpos]=nodeleft;
}
else{
leftmost[segpos]=sze;
}
}
}
void update(int arrpos, int val, int segpos, int nodeleft, int noderight){
if(nodeleft!=noderight){
int nodemid = (nodeleft+noderight)/2;
if(arrpos<=nodemid){
update(arrpos, val, 2*segpos+1, nodeleft, nodemid);
}
else{
update(arrpos, val, 2*segpos+2, nodemid+1, noderight);
}
leftmost[segpos]=min(leftmost[2*segpos+1], leftmost[2*segpos+2]);
}
else{
array[nodeleft]+=val;
if(array[nodeleft]!=0){
leftmost[segpos]=nodeleft;
}
else{
leftmost[segpos]=sze;
}
}
}
int query(int queryleft, int queryright, int segpos, int nodeleft, int noderight){
if(queryleft==nodeleft && queryright==noderight){
return leftmost[segpos];
}
else{
int nodemid = (nodeleft+noderight)/2;
if(queryright<=nodemid){
return query(queryleft, queryright, 2*segpos+1, nodeleft, nodemid);
}
else if(queryleft>nodemid){
return query(queryleft, queryright, 2*segpos+2, nodemid+1, noderight);
}
else{
int temp = query(queryleft, nodemid, 2*segpos+1, nodeleft, nodemid);
if(temp!=sze){
return temp;
}
else{
return query(nodemid+1, queryright, 2*segpos+2, nodemid+1, noderight);
}
}
}
}
};
int mmin(int a, int b, int c, int d){
return min(a, min(b, min(c, d)));
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
int arr[2][n];
long long fincount = 0;
for(int i=0; i<n; i++){
arr[0][i]=0;
arr[1][i]=0;
}
for(int i=0; i<2*n; i++){
long long a, b;
cin >> a >> b;
if(a<=1){
if(b>=2){
arr[1][0]++;
fincount+=b-1-a;
}
else{
arr[0][0]++;
fincount+=2-b-a;
}
}
else if(a>=n){
if(b>=2){
arr[1][n-1]++;
fincount+=b-2+a-n;
}
else{
arr[0][n-1]++;
fincount+=a-n+1-b;
}
}
else{
if(b>=2){
arr[1][a-1]++;
fincount+=b-2;
}
else{
arr[0][a-1]++;
fincount+=1-b;
}
}
}
for(int i=0; i<n; i++){
while(arr[0][i]>1){
int pos1 = i;
int pos2 = i;
int pos3 = i;
int pos4 = i;
while(pos1>=0 && arr[0][pos1]>=1){
pos1--;
}
while(pos2<n && arr[0][pos2]>=1){
pos2++;
}
while(pos3>=0 && arr[1][pos3]>=1){
pos3--;
}
while(pos4<n && arr[1][pos4]>=1){
pos4++;
}
if(pos1==-1){
pos1=-1000000;
}
if(pos2==n){
pos2=1000000;
}
if(pos3==-1){
pos3=-1000000;
}
if(pos4==n){
pos4=1000000;
}
int minn = mmin(i-pos1, pos2-i, i-pos3+1, pos4-i+1);
if(i-pos1==minn){
arr[0][pos1]++;
arr[0][i]--;
fincount+=i-pos1;
}
else if(i-pos3+1==minn){
arr[1][pos3]++;
arr[0][i]--;
fincount+=i-pos3+1;
}
else if(pos2-i==minn){
arr[0][pos2]++;
arr[0][i]--;
fincount+=pos2-i;
}
else{
arr[1][pos4]++;
arr[0][i]--;
fincount+=pos4-i+1;
}
}
while(arr[1][i]>1){
int pos1 = i;
int pos2 = i;
int pos3 = i;
int pos4 = i;
while(pos1>=0 && arr[0][pos1]>=1){
pos1--;
}
while(pos2<n && arr[0][pos2]>=1){
pos2++;
}
while(pos3>=0 && arr[1][pos3]>=1){
pos3--;
}
while(pos4<n && arr[1][pos4]>=1){
pos4++;
}
if(pos1==-1){
pos1=-1000000;
}
if(pos2==n){
pos2=1000000;
}
if(pos3==-1){
pos3=-1000000;
}
if(pos4==n){
pos4=1000000;
}
int minn = mmin(i-pos1+1, pos2-i+1, i-pos3, pos4-i);
if(i-pos3==minn){
arr[1][pos3]++;
arr[1][i]--;
fincount+=i-pos3;
}
else if(i-pos1+1==minn){
arr[0][pos1]++;
arr[1][i]--;
fincount+=i-pos1+1;
}
else if(pos4-i==minn){
arr[1][pos4]++;
arr[1][i]--;
fincount+=pos4-i;
}
else{
arr[0][pos2]++;
arr[1][i]--;
fincount+=pos2-i+1;
}
}
}
cout << fincount << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
320 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
320 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
320 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
