oj.uz

Submission #463865

# Submission time Handle Problem Language Result Execution time Memory
463865 2021-08-11T22:57:57 Z TeaTime Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 1 ms 332 KB 
//#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];
int seg2[SZ * 4];

void upd2(int v, int l, int r, int pos, int val = 0) {
    if (l == r - 1) {
        seg2[v] = val;
    } else {
        int mid = (l + r) / 2;
        if (pos < mid) {
            upd2(v * 2 + 1, l, mid, pos, val);
        } else {
            upd2(v * 2 + 2, mid, r, pos, val);
        }

        seg2[v] = seg2[v * 2 + 1] + seg2[v * 2 + 2];
    }
}
int ask2(int v, int l, int r, int askl, int askr) {
    if (l >= askr || r <= askl) return 0;

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

    int mid = (l + r) / 2;
    int q = ask2(v * 2 + 1, l, mid, askl, askr), q2 = ask2(v * 2 + 2, mid, r, askl, askr);
    return  q + q2;
}
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]);
        upd2(0, 0, SZ, 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;
        /*if (st.size() > 2 && (*(--(--st.end()))).first >= 2) {
            cur = (*(--(--st.end())));
            st.erase(--(--st.end()));
        } else {*/
            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);
        upd2(0, 0, SZ, 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 = 0;
            pair<ll, ll> sm = ask(0, 0, SZ, lftPos2 + 1, lftPos + 1);
            pair<ll, ll> sm2 = ask(0, 0, SZ, lftPos, lftPos + 1);
            
            ll lng = ask2(0, 0, SZ, 0, lftPos + 1);
            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);
            
            if (sm.first + sm.second < lng) {
                st.erase({ sm2.first + sm2.second, lftPos });
                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 = ask2(0, 0, SZ, 0, lftPos + 1);
                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 = n + 1;
            pair<ll, ll> sm = ask(0, 0, SZ, lftPos, lftPos2);
            pair<ll, ll> sm2 = ask(0, 0, SZ, lftPos, lftPos + 1);
            
            ll lng = ask2(0, 0, SZ, lftPos, n + 1);
            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);

            if (sm.first + sm.second < lng) {
                st.erase({ sm2.first + sm2.second, lftPos });
                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 = ask2(0, 0, SZ, lftPos, n + 1);
                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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Incorrect 1 ms 332 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Incorrect 1 ms 332 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Incorrect 1 ms 332 KB Output isn't correct
15 Halted 0 ms 0 KB -