Submission #463855

#	Time	Username	Problem	Language	Result	Execution time	Memory
463855		whoiam	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	68 ms	5688 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

#define range(i, n) for (int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define ar array
using namespace std;

// using namespace __gnu_pbds;
/*
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
*/

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;

const int INFi = 1e9 + 5;
const int maxN = 2e5 + 5;
const int md = 998244353;
const ll INF = 2e18;

double getTime() { return clock() / (double) CLOCKS_PER_SEC; }

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> cnt(2, vector<int> (n + 1));
    ll ans = 0;
    range(_, 2 * n) {
        int x, y;
        cin >> x >> y;
        if (y < 1) {
            ans += 1 - y;
            y = 1;
        } else if (y > 2) {
            ans += y - 2;
            y = 2;
        }
        if (x < 1) {
            ans += 1 - x;
            x = 1;
        } else if (x > n) {
            ans += x - n;
            x = n;
        }
        cnt[y - 1][x]++;
    }
    n++;
    int i = 0, j = 0;
    cnt[0][0] = cnt[1][0] = 1;
    for(int e = 1; e < n; ++e) {
        if (i == e - 1 && j == e - 1) {
            ans += cnt[0][i] - 1;
            cnt[0][e] += cnt[0][i] - 1;
            cnt[0][i] = 1;
            ans += cnt[1][j] - 1;
            cnt[1][e] += cnt[1][j] - 1;
            cnt[1][j] = 1;
        } else {
            while(cnt[0][e] && i != e - 1) {
                i++;
                cnt[0][i] = 1;
                cnt[0][e]--;
                ans += e - i;
            }
            while(cnt[1][e] && j != e - 1) {
                j++;
                cnt[1][j] = 1;
                cnt[1][e]--;
                ans += e - j;
            }
        }
        if (j == e - 1 && cnt[1][e]) j++;
        if (i == e - 1 && cnt[0][e]) i++;
        while(cnt[0][e] > 1 && j != e) {
            j++;
            cnt[0][e]--;
            cnt[1][j] = 1;
            ans += e - j + 1;
        }
        while(cnt[1][e] > 1 && i != e) {
            i++;
            cnt[1][e]--;
            cnt[0][i] = 1;
            ans += e - i + 1;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int tests = 1;
//    cin >> tests;
    range(_, tests) {
        solve();
    }
    return 0;
}

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