Submission #243445

#	Time	Username	Problem	Language	Result	Execution time	Memory
243445		thecodingwizard	Coin Collecting (JOI19_ho_t4)	C++11	100 / 100	284 ms	5752 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n; cin >> n;
    long long ans = 0;
    int top[n+2], bot[n+2];
    for (int i = 1; i <= n; i++) top[i] = bot[i] = 0;
    for (int i = 0; i < 2*n; i++) {
        int a, b; cin >> a >> b;
        if (a < 1) {
            ans += 1-a;
            a = 1;
        }
        if (a > n) {
            ans += a - n;
            a = n;
        }
        if (b < 1) {
            ans += 1 - b;
            b = 1;
        }
        if (b > 2) {
            ans += b - 2;
            b = 2;
        }
        if (b == 1) bot[a]++;
        else top[a]++;
    }
    int topIdx = 1, botIdx = 1;
    for (int i = 1; i <= n; i++) {
        while (topIdx <= i && top[i] > 0) {
            ans += i - topIdx;
            topIdx++;
            top[i]--;
        }
        while (botIdx <= i && bot[i] > 0) {
            ans += i - botIdx;
            botIdx++;
            bot[i]--;
        }
        while (botIdx <= i && top[i] > 0) {
            ans += i - botIdx + 1;
            botIdx++;
            top[i]--;
        }
        while (topIdx <= i && bot[i] > 0) {
            ans += i - topIdx + 1;
            topIdx++;
            bot[i]--;
        }
        top[i+1] += top[i];
        bot[i+1] += bot[i];
        ans += top[i] + bot[i];
    }
    cout << ans << endl;

    return 0;
}

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