//bit chass 1
#include <bits/stdc++.h>
#define x first
#define y second
#define el "\n"
#define ll long long
#define pb push_back
#define pll pair <ll, ll>
#define pii pair <int, int>
#define all(x) x.begin(), x.end()
#define lcm(x,y) x * y / __gcd(x, y)
#define ibase ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
const int N = 1e5 + 5, inf = 1e9 + 7, M = 2e6, MM = 2e6 + 5, K = 300;
const ll MI = 2e18;
const double P = 3.14;
int x[N], y[N], c[3][N];
void solve() {
memset(c, 0, sizeof c);
int n;
ll ans = 0;
cin >> n;
for (int i = 1; i <= 2 * n; i++) {
cin >> x[i] >> y[i];
if (1 <= x[i] && x[i] <= n && 1 <= y[i] && y[i] <= 2)
c[y[i]][x[i]]++;
else if (1 <= x[i] && x[i] <= n) {
if (y <= 0)
c[1][x[i]]++, ans += 1 - y[i];
else
c[2][x[i]]++, ans += y[i] - 2;
}
else if (1 <= y[i] && y[i] <= 2) {
if (x[i] <= 0)
c[y[i]][1]++, ans += 1 - x[i];
else
c[y[i]][n]++, ans += x[i] - n;
}
else {
if (x[i] <= 0 && y[i] <= 0)
c[1][1]++, ans += 1 - y[i] + 1 - x[i];
if (x[i] <= 0 && y[i] > 2)
c[2][1]++, ans += 1 - x[i] + y[i] - 2;
if (x[i] > n && y[i] <= 0)
c[1][n]++, ans += x[i] - n + 1 - y[i];
if (x[i] > n && y[i] > 2)
c[2][n]++, ans += x[i] - n + y[i] - 2;// cout << x[i] << ' ' << y[i] << el;;
}
}
// cout << ans << el;
// for (int i = 2; i >= 1; i--) {
// for (int j = 1; j <= n; j++)
// cout << c[i][j] << ' ';
// cout << el;
// }
int r = 1;
for (int i = 1; i <= n; i++) {
r = max(i, r);
if (c[1][i] && c[2][i]) {
c[1][i]--;
c[2][i]--;
ans += c[1][i];
ans += c[2][i];
c[1][i + 1] += c[1][i];
c[2][i + 1] += c[2][i];
}
else if (c[1][i]) {
if (c[1][i] >= 2) {
c[2][i]++;
ans++;
c[1][i] -= 2;
c[1][i + 1] += c[1][i];
ans += c[1][i];
}
else {
r = max(r, i + 1);
while (c[1][r] + c[2][r] == 0)
r++;
if (c[2][r]) {
ans += r - i;
c[2][r]--;
c[2][i]++;
}
else {
ans += r - i + 1;
c[1][r]--;
c[2][i]++;
}
}
}
else if (c[2][i]) {
if (c[2][i] >= 2) {
c[1][i]++;
ans++;
c[2][i] -= 2;
c[2][i + 1] += c[2][i];
ans += c[2][i];
}
else {
r = max(r, i + 1);
while (c[1][r] + c[2][r] == 0)
r++;
if (c[1][r]) {
ans += r - i;
c[1][i]++;
c[1][r]--;
}
else {
ans += r - i + 1;
c[2][r]--;
c[1][i]++;
}
}
}
else {
while (c[1][r] + c[2][r] == 0)
r++;
if (c[1][r]) {
c[1][i]++;
ans += r - i;
c[1][r]--;
if (c[2][r]) {
c[2][i]++;
ans += r - i;
c[2][r]--;
}
else {
while (c[1][r] + c[2][r] == 0)
r++;
if (c[2][r]) {
ans += r - i;
c[2][r]--;
c[2][i]++;
}
else {
ans += r - i + 1;
c[1][r]--;
c[2][i]++;
}
}
}
else if (c[2][r]) {
c[2][i]++;
ans += r - i;
c[2][r]--;
if (c[1][r]) {
c[1][i]++;
ans += r - i;
c[1][r]--;
}
else {
while (c[1][r] + c[2][r] == 0)
r++;
if (c[1][r]) {
ans += r - i;
c[1][i]++;
c[1][r]--;
}
else {
ans += r - i + 1;
c[2][r]--;
c[1][i]++;
}
}
}
}
}
cout << ans;
}
int main() {
ibase;
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++) {
// cout << "Case " << i << ": ";
solve();
cout << el;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
1484 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
1484 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
1484 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
