#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<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+1;
}
}
}
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+1;
}
}
}
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{
return min(query(queryleft, nodemid, 2*segpos+1, nodeleft, nodemid), query(nodemid+1, queryright, 2*segpos+2, nodemid+1, noderight));
}
}
}
};
int main(){
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;
}
}
}
segmenttree first(n, arr[0]);
segmenttree second(n, arr[1]);
for(int i=0; i<n; i++){
if(arr[0][i]!=1){
if(arr[0][i]>1){
if(arr[1][i]==0){
int temp = arr[0][i];
arr[1][i]++;
second.update(i, 1, 0, 0, n-1);
arr[0][i+1]+=temp-2;
first.update(i+1, temp-2, 0, 0, n-1);
arr[0][i]-=temp-1;
first.update(i, 1-temp, 0, 0, n-1);
fincount+=temp-1;
}
else{
int temp = arr[0][i];
arr[0][i+1]+=temp-1;
first.update(i+1, temp-1, 0, 0, n-1);
arr[0][i]-=temp-1;
first.update(i, 1-temp, 0, 0, n-1);
fincount+=temp-1;
}
}
else{
int pos1 = first.query(i+1, n-1, 0, 0, n-1);
int pos2 = second.query(i, n-1, 0, 0, n-1);
if(pos1<=pos2+1){
arr[0][i]+=1;
first.update(i, 1, 0, 0, n-1);
arr[0][pos1]-=1;
first.update(pos1, -1, 0, 0, n-1);
fincount+=pos1-i;
}
else{
arr[0][i]+=1;
first.update(i, 1, 0, 0, n-1);
arr[1][pos2]-=1;
second.update(pos2, -1, 0, 0, n-1);
fincount+=pos2-i+1;
}
}
}
if(arr[1][i]!=1){
if(arr[1][i]>1){
int temp = arr[0][i];
arr[0][i+1]+=temp-1;
first.update(i+1, temp-1, 0, 0, n-1);
arr[0][i]-=temp-1;
first.update(i, 1-temp, 0, 0, n-1);
fincount+=temp-1;
}
else{
int pos1 = first.query(i, n-1, 0, 0, n-1);
int pos2 = second.query(i+1, n-1, 0, 0, n-1);
if(pos1+1<pos2){
arr[1][i]+=1;
second.update(i, 1, 0, 0, n-1);
arr[0][pos1]-=1;
first.update(pos1, -1, 0, 0, n-1);
fincount+=pos1-i+1;
}
else{
arr[1][i]+=1;
second.update(i, 1, 0, 0, n-1);
arr[1][pos2]-=1;
second.update(pos2, -1, 0, 0, n-1);
fincount+=pos2-i;
}
}
}
}
cout << fincount << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
296 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Execution timed out |
1090 ms |
212 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
296 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Execution timed out |
1090 ms |
212 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
296 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Execution timed out |
1090 ms |
212 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
