#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int N=100007;
int a[N][2];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,x,y;
cin>>n;
ll ans=0;
for(int i=1;i<=2*n;i++)
{
cin>>x>>y;
bool b;
if(y>1)
{
ans+=y-2;
b=1;
}
else
{
ans+=1-y;
b=0;
}
if(x<1)
{
ans+=1-x;
a[1][b]++;
}
else if(x>n)
{
ans+=x-n;
a[n][b]++;
}
else
{
a[x][b]++;
}
}
int j=0;
int c0=0,c1=0;
for(int i=1;i<=n;i++)
{
c0+=a[i][0];
c1+=a[i][1];
int d=i-j;
if(c0+c1>=d*2)
{
int x=max(0,c0-d-max(0,d-c1));
a[i][0]-=x;
a[i+1][0]+=x;
ans+=x;
x=max(0,c1-d-max(0,d-c0));
a[i][1]-=x;
a[i+1][1]+=x;
ans+=x;
for(int l=i;l>j;l--)
{
if(a[l][0]==0)
{
a[l][1]--;
a[l][0]++;
ans++;
}
if(a[l][1]==0)
{
a[l][0]--;
a[l][1]++;
ans++;
}
a[l][0]--;
a[l][1]--;
ans+=a[l][0]+a[l][1];
a[l-1][0]+=a[l][0];
a[l-1][1]+=a[l][1];
a[l][0]=0;
a[l][1]=0;
}
j=i;
c0=0;
c1=0;
}
}
cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
328 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
328 KB |
Output is correct |
14 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
328 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
328 KB |
Output is correct |
14 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
328 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
328 KB |
Output is correct |
14 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |