Submission #1089645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089645		efishel	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	35 ms	9092 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

ll freq[100005][3];

// ii operator+ (const ii a, const ii b) { return ii{ a.first + b.first, a.second + b.second, }; }
// ii operator- (const ii a, const ii b) { return ii{ a.first - b.first, a.second - b.second, }; }
// ii operator+= (ii &a, const ii b) { return a = a + b; }
// ostream& operator<< (ostream &os, const ii a) { return os << a.first << ' ' << a.second; }

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n;
    cin >> n;
    vii ve(2*n);
    for (auto &[x, y] : ve) cin >> x >> y;
    ll ans = 0;
    auto fclamp = [&](ll l, ll r, ll &val) {
        if (val < l) { ans += l-val; val = l; }
        if (val > r) { ans += val-r; val = r; }
    };
    for (auto &[x, y] : ve) {
        fclamp(1, n, x);
        fclamp(1, 2, y);
        freq[x][y]++;
    }
    ll c1 = 0, c2 = 0; // ci = until the current prefix, how many free coins are in row i (negative to show lack of)
    for (ll i = 1; i <= n; i++) {
        c1 += freq[i][1]-1; // -1 = consumes one
        c2 += freq[i][2]-1; // -1 = consumes one
        // 4 cases, only in 2 we do something
        if (c1 < 0 && c2 > 0) { // shortage in c1 that's satisfied by c2
            ll t = min(-c1, c2);
            // ll t = 1;
            c1 += t; c2 -= t;
            ans += t;
        } else if (c2 < 0 && c1 > 0) { // vice versa
            ll t = min(-c2, c1);
            // ll t = 1;
            c2 += t; c1 -= t;
            ans += t;
        }
        // ans += abs(val) because if val is positive, #val coins have to move out, if val is negative, #-val coins have to eventually come in
        ans += abs(c1);
        ans += abs(c2);
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63