//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
template<>
struct std::hash<pair<ll, ll>> {
ll operator() (pair<ll, ll> p) const {
return ((__int128)p.first * MOD + p.second) % INF64;
}
};
void solve() {
ll n;
cin >> n;
vector<ll> col1(n, 0), col2(n, 0);
ll ans = 0;
for (ll i = 0; i < n * 2; i++) {
ll x, y;
cin >> x >> y;
if (x < 1) {
ans += 1 - x;
x = 1;
}
if (x > n) {
ans += x - n;
x = n;
}
x--;
if (y >= 2) {
col2[x]++;
ans += y - 2;
} else {
col1[x]++;
ans += 1 - y;
}
}
deque<ll> all1, all2;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < col1[i]; j++) {
all1.push_back(i);
}
for (ll j = 0; j < col2[i]; j++) {
all2.push_back(i);
}
}
ll nc1 = 0, nc2 = 0;
for (ll i = 0; i < n; i++) {
ans += nc1 + nc2;
while (!all1.empty() && all1.front() == i) {
nc1++;
all1.pop_front();
}
while (!all2.empty() && all2.front() == i) {
nc2++;
all2.pop_front();
}
bool b1 = false, b2 = false;
if (nc1) {
nc1--;
b1 = true;
}
if (nc2) {
nc2--;
b2 = true;
}
if (!b1 && !b2) {
ll ba = INF32;
ll d1 = 0, d2 = 0;
if (all1.size() >= 2) {
if (assign_min(ba, all1[0] + all1[1] - i * 2 + 1)) {
d1 = 2;
}
}
if (all2.size() >= 2) {
if (assign_min(ba, all2[0] + all2[1] - i * 2 + 1)) {
d1 = 0;
d2 = 2;
}
}
if (!all1.empty() && !all2.empty()) {
if (assign_min(ba, all1[0] + all2[0] - i * 2)) {
d1 = 1;
d2 = 1;
}
}
ans += ba;
for (ll i = 0; i < d1; i++) {
all1.pop_front();
}
for (ll i = 0; i < d2; i++) {
all2.pop_front();
}
b1 = true;
b2 = true;
}
if (!b1) {
if (nc2) {
nc2--;
ans++;
continue;
}
ll ba = INF32;
bool u1;
if (!all1.empty()) {
if (assign_min(ba, all1[0] - i)) {
u1 = true;
}
}
if (!all2.empty()) {
if (assign_min(ba, all2[0] - i + 1)) {
u1 = false;
}
}
ans += ba;
if (u1) {
all1.pop_front();
} else {
all2.pop_front();
}
}
if (!b2) {
if (nc1) {
nc1--;
ans++;
continue;
}
ll ba = INF32;
bool u1;
if (!all1.empty()) {
if (assign_min(ba, all1[0] - i + 1)) {
u1 = true;
}
}
if (!all2.empty()) {
if (assign_min(ba, all2[0] - i)) {
u1 = false;
}
}
ans += ba;
if (u1) {
all1.pop_front();
} else {
all2.pop_front();
}
}
}
cout << ans << '\n';
}
int main() {
if (IS_FILE) {
freopen("", "r", stdin);
freopen("", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
if (IS_TEST_CASES) {
cin >> t;
}
for (ll i = 0; i < t; i++) {
solve();
}
}
Compilation message
joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:190:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
190 | freopen("", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t4.cpp:191:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
191 | freopen("", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t4.cpp: In function 'void solve()':
joi2019_ho_t4.cpp:178:25: warning: 'u1' may be used uninitialized in this function [-Wmaybe-uninitialized]
178 | if (u1) {
| ^~
joi2019_ho_t4.cpp:153:25: warning: 'u1' may be used uninitialized in this function [-Wmaybe-uninitialized]
153 | if (u1) {
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
548 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
548 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
548 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
