Submission #1089625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089625		efishel	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	468 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][2];

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; }

struct Fenwick {
    vii tree;
    ll n;

    Fenwick (ll n): tree(n), n(n) {}

    void update (ll id, ii val) {
        for (; id < n; id |= id+1) tree[id] += val;
    }

    ll fquery (ll id) { auto [y0, y1] = query(id); return y0 + y1; }
    ii query (ll id) {
        ii ans = ii{ 0, 0 };
        for (; id >= 0; id &= id+1, id--) ans += tree[id];
        return ans;
    }
    ii oquery (ll id) { return query(id) - query(id-1); }
};

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-1][y-1]++;
    }
    Fenwick ft(n);
    for (ll i = 0; i < n; i++) ft.update(i, ii{ freq[i][0], freq[i][1] });
    auto excess0toI = [&](ll i) {
        return ft.fquery(i) - 2*(i+1);
    };
    auto fstab = [&](ll i) { // stab as in stabilize
        auto [y0, y1] = ft.oquery(i);
        assert(y0 + y1 == 2);
        ll ny0 = y0, ny1 = y1;
        if (ny0 == 0) { ny0++; ny1--; ans++; }
        if (ny1 == 0) { ny1++; ny0--; ans++; }
        ft.update(i, ii{ ny0-y0, ny1-y1 });
    };
    auto fgetM = [&](ll i, ll howM) -> ii {
        auto [y0, y1] = ft.oquery(i);
        ll ny0 = y0, ny1 = y1;
        {ll g0 = min(howM, ny0-1);
        ny0 -= g0;
        howM -= g0;}
        {ll g1 = min(howM, ny1-1);
        ny1 -= g1;
        howM -= g1;}
        assert(howM == 0);
        ft.update(i, ii{ ny0-y0, ny1-y1 });
        ans += y0-ny0 + y1-ny1;
        return ii{
            y0-ny0,
            y1-ny1
        };
    };
    // for (ll i = 0; i < n; i++) {
    //     auto [y0, y1] = ft.oquery(i);
    //     // cerr << y0 << ' ' << y1 << '\n';
    // }
    for (ll i = 0; i < n-1; i++) { // sweep to right
        ll exc = excess0toI(i);
        if (exc > 0) {
            // cerr << "must move right " << exc << " from " << i << " to " << i+1 << '\n';
            ft.update(i+1, fgetM(i, exc));
        }
    }
    for (ll i = n-1; i >= 1; i--) { // sweep to left
        ll exc = -excess0toI(i-1);
        if (exc > 0) {
            // cerr << "must move  left " << exc << " from " << i << " to " << i-1 << '\n';
            ft.update(i-1, fgetM(i, exc));
        }
    }
    for (ll i = 0; i < n; i++) {
        fstab(i);
    }
    // for (ll i = 0; i < n; i++) {
    //     auto [y0, y1] = ft.oquery(i);
    //     // cerr << y0 << ' ' << y1 << '\n';
    // }
    // function <void(ll)> solve = [&](ll i) {
    //     if (i == n-1) {
    //         fstab(i);
    //         return;
    //     }
    //     ll exc = excess0toI(i);
    //     if (exc > 0) { // excess in the left
    //         cerr << i << ": exc left, move right\n";
    //         fstab(i);
    //         ft.update(i+1, fgetex(i));
    //         cerr << ft.oquery(i) << "  " << ft.oquery(i+1) << endl;
    //         solve(i+1);
    //         fstab(i);
    //     } else {
    //         cerr << i << ": exc right, move left.. wait\n";
    //         solve(i+1);
    //         cerr << i << ": exc right, move left.. came back\n";
    //         fstab(i+1);
    //         ft.update(i, fgetex(i+1));
    //         fstab(i);
    //     }
    //     // assert((excess0toI(i) == 0));
    //     // assert((ft.oquery(i) == ii{ 1, 1 }));
    // };
    // solve(0);
    cout << ans << '\n';
    return 0;
}

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