Submission #463857

#	Time	Username	Problem	Language	Result	Execution time	Memory
463857		TeaTime	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	332 KiB

joi2019_ho_t4

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SZ = 2e5 + 100;

#define int ll
ll n;
vector<pair<ll, ll>> vec;

ll svd[SZ][2];
pair<int, int> seg[SZ * 4];

void upd(int v, int l, int r, int pos, int val, int val2) {
    if (l == r - 1) {
        seg[v].first += val;
        seg[v].second += val2;
    } else {
        int mid = (l + r) / 2;
        if (pos < mid) {
            upd(v * 2 + 1, l, mid, pos, val, val2);
        } else {
            upd(v * 2 + 2, mid, r, pos, val, val2);
        }

        seg[v] = { seg[v * 2 + 1].first + seg[v * 2 + 2].first, seg[v * 2 + 1].second + seg[v * 2 + 2].second };
    }
}

pair<int, int> ask(int v, int l, int r, int askl, int askr) {
    if (l >= askr || r <= askl) return { 0, 0 };

    if (askl <= l && r <= askr) return seg[v];

    int mid = (l + r) / 2;
    pair<int, int> q = ask(v * 2 + 1, l, mid, askl, askr), q2 = ask(v * 2 + 2, mid, r, askl, askr);
    return  { q.first + q2.first, q.second + q2.second };
}

signed main() {
    fastInp;

    cin >> n;

    vec.resize(n * 2);

    for (int i = 0; i < n * 2; i++) cin >> vec[i].first >> vec[i].second;

    ll ans = 0;

    set<ll> hv, er;
    for (int i = 0; i < n * 2; i++) {
        if (vec[i].first <= 1) {
            ans += abs(vec[i].first - 1);
            vec[i].first = 1;
        }
        if (vec[i].first >= n) {
            ans += abs(vec[i].first - n);
            vec[i].first = n;
        }
        if (vec[i].second <= 1) {
            ans += abs(vec[i].second - 1);
            vec[i].second = 1;
        }
        if (vec[i].second >= 2) {
            ans += abs(vec[i].second - 2);
            vec[i].second = 2;
        }

        svd[vec[i].first][vec[i].second - 1]++;
    }

    for (int i = 1; i <= n; i++) {
        hv.insert(i);
        upd(0, 0, SZ, i, svd[i][0], svd[i][1]);
    }

    set<pair<ll, ll>> st;
    for (int i = 1; i <= n; i++) {
        st.insert({ svd[i][0] + svd[i][1], i });
    }

    er.insert(0);
    er.insert(n + 1);
    ll sm = n * 2;
    for (int i = 0; i < n; i++) {
        if (seg[0].first + seg[0].second != sm) return 1;
        sm -= 2;
        pair<ll, ll> cur = (*(--st.end()));
        st.erase(--st.end());
        pair<ll, ll> vals = ask(0, 0, SZ, cur.second, cur.second + 1);
        hv.erase(cur.second);
        er.insert(cur.second);
     
        upd(0, 0, SZ, cur.second, -vals.first, -vals.second);

        if (vals.first > 0 && vals.second > 0) {
            vals.first--;
            vals.second--;
        } else {
            if (vals.first > 0) vals.first -= 2;
            if (vals.second > 0) vals.second -= 2;
            ans++;
        }

        if (hv.lower_bound(cur.second) != hv.begin()) {
            ll lftPos = *(--hv.lower_bound(cur.second));
            ll lftPos2 = *(--er.lower_bound(lftPos));
            pair<ll, ll> sm = ask(0, 0, SZ, lftPos2 + 1, lftPos + 1);
            pair<ll, ll> sm2 = ask(0, 0, SZ, lftPos, lftPos + 1);
            st.erase({ sm2.first + sm2.second, lftPos });
            ll lng = lftPos - lftPos2;
            lng *= 2;

            ll q = min(vals.first, max(sm.second, sm.first) - sm.first);
            ll q2 = min(vals.second, max(sm.second, sm.first) - sm.second);
            
            upd(0, 0, SZ, lftPos, q, q2);
            vals.first -= q;
            vals.second -= q2;

            sm.first += q;
            sm.second += q2;

            ans += q * abs(cur.second - lftPos);
            ans += q2 * abs(cur.second - lftPos);
            lng -= (sm.first + sm.second);

            ll mn = min(vals.first, vals.second);
            mn = min(mn, lng / 2);

            upd(0, 0, SZ, lftPos, mn, mn);
            vals.first -= mn;
            vals.second -= mn;

            sm.first += mn;
            sm.second += mn;

            ans += mn * abs(cur.second - lftPos);
            ans += mn * abs(cur.second - lftPos);
            lng = lftPos - lftPos2;
            lng *= 2;
            lng -= (sm.first + sm.second);

            mn = min(vals.first, lng);
            lng -= mn;
            upd(0, 0, SZ, lftPos, mn, 0);
            vals.first -= mn;
            sm.first += mn;
            ans += mn * abs(cur.second - lftPos);

            mn = min(vals.second, lng);
            lng -= mn;
            upd(0, 0, SZ, lftPos, 0, mn);
            vals.second -= mn;
            sm.second += mn;
            ans += mn * abs(cur.second - lftPos);

            sm2 = ask(0, 0, SZ, lftPos, lftPos + 1);
            st.insert({ sm2.first + sm2.second, lftPos });
        }

        if (hv.upper_bound(cur.second) != hv.end()) {
            ll lftPos = *(hv.upper_bound(cur.second));
            ll lftPos2 = *(er.upper_bound(lftPos));
            pair<ll, ll> sm = ask(0, 0, SZ, lftPos, lftPos2);
            pair<ll, ll> sm2 = ask(0, 0, SZ, lftPos, lftPos + 1);
            st.erase({ sm2.first + sm2.second, lftPos });
            ll lng = lftPos2 - lftPos;
            lng *= 2;

            ll q = min(vals.first, max(sm.second, sm.first) - sm.first);
            ll q2 = min(vals.second, max(sm.second, sm.first) - sm.second);

            upd(0, 0, SZ, lftPos, q, q2);
            vals.first -= q;
            vals.second -= q2;

            sm.first += q;
            sm.second += q2;

            ans += q * abs(cur.second - lftPos);
            ans += q2 * abs(cur.second - lftPos);
            lng -= (sm.first + sm.second);

            ll mn = min(vals.first, vals.second);
            mn = min(mn, lng / 2);

            upd(0, 0, SZ, lftPos, mn, mn);
            vals.first -= mn;
            vals.second -= mn;

            sm.first += mn;
            sm.second += mn;

            ans += mn * abs(cur.second - lftPos);
            ans += mn * abs(cur.second - lftPos);
            lng = lftPos2 - lftPos;
            lng *= 2;
            lng -= (sm.first + sm.second);

            mn = min(vals.first, lng);
            lng -= mn;
            upd(0, 0, SZ, lftPos, mn, 0);
            vals.first -= mn;
            sm.first += mn;
            ans += mn * abs(cur.second - lftPos);

            mn = min(vals.second, lng);
            lng -= mn;
            upd(0, 0, SZ, lftPos, 0, mn);
            vals.second -= mn;
            sm.second += mn;
            ans += mn * abs(cur.second - lftPos);

            sm2 = ask(0, 0, SZ, lftPos, lftPos + 1);
            st.insert({ sm2.first + sm2.second, lftPos });
        }
    }

    cout << ans;

    return 0;
}

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