Submission #463875

#	Time	Username	Problem	Language	Result	Execution time	Memory
463875		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];
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]++;
    }

    pair<ll, ll> pt = { 1, 1 };
    for (int i = 1; i <= n; i++) {
        while (pt.first < i && svd[pt.first][0] == 0 && svd[i][0] > 0) {
            svd[pt.first][0]++;
            svd[i][0]--;
            ans += abs(i - pt.first);
            pt.first++;
        }
        while (pt.second < i && svd[pt.second][1] == 0 && svd[i][1] > 0) {
            svd[pt.second][1]++;
            svd[i][1]--;
            ans += abs(i - pt.second);
            pt.second++;
        }
        while (pt.first < i && svd[pt.first][0] == 0 && svd[i][1] > 0) {
            svd[pt.first][0]++;
            svd[i][1]--;
            ans += abs(i - pt.first) + 1;
            pt.first++;
        }
        while (pt.second < i && svd[pt.second][1] == 0 && svd[i][0] > 0) {
            svd[pt.second][1]++;
            svd[i][0]--;
            ans += abs(i - pt.second) + 1;
            pt.second++;
        }
        if (svd[i][0] > 1) {
            svd[i + 1][0] += svd[i][0] - 1;
            ans += svd[i][0] - 1;
        }
        if (svd[i][1] > 1) {
            svd[i + 1][1] += svd[i][1] - 1;
            ans += svd[i][1] - 1;
        }
    }

    cout << ans;

    return 0;
}

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