Submission #1361860

#TimeUsernameProblemLanguageResultExecution timeMemory
1361860gayCoin Collecting (JOI19_ho_t4)C++20
100 / 100
28 ms8944 KiB
#include <bits/stdc++.h>

using namespace std;

using ld = long double;
using ll = long long;

const ll INF = 3e18, MOD = 1e9 + 7;

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q = 1;
    while (q--) {
        solve();
    }
}

void solve() {
    ll n; cin >> n;
    vector<pair<ll, ll>> a(2 * n);
    ll ans = 0;
    for (int i = 0; i < 2 * n; i++) {
        cin >> a[i].first >> a[i].second;
        if (abs(1 - a[i].second) < abs(2 - a[i].second)) {
            ans += abs(1 - a[i].second);
            a[i].second = 1;
        } else {
            ans += abs(2 - a[i].second);
            a[i].second = 2;
        }
        if (a[i].first < 1) {
            ans += (1 - a[i].first);
            a[i].first = 1;
        }
        if (a[i].first > n) {
            ans += (a[i].first - n);
            a[i].first = n;
        }
    }
    vector<vector<ll>> cnt(n, vector<ll>(2));
    for (int i = 0; i < 2 * n; i++) {
        cnt[a[i].first - 1][a[i].second - 1]++;
    }
    ll b1 = 0, b2 = 0, r = 0;
    for (int i = 0; i < n; ++i) {
        b1 += cnt[i][0] - 1;
        b2 += cnt[i][1] - 1;
        if (b1 > 0 && b2 < 0) {
            ll t = min(b1, -b2);
            r += t; b1 -= t; b2 += t;
        } else if (b1 < 0 && b2 > 0) {
            ll t = min(-b1, b2);
            r += t; b1 += t; b2 -= t;
        }
        r += abs(b1) + abs(b2);
    }
    cout << r + ans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...