제출 #523440

#제출 시각아이디문제언어결과실행 시간메모리
523440MonarchuwuCoin Collecting (JOI19_ho_t4)C++17
100 / 100
70 ms5700 KiB
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;

const int N = 1e5 + 9;
int n, cnt[4][N];

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;
    ll sum(0);
    for (int i = 1, x, y; i <= n * 2; ++i) {
        cin >> x >> y;
        if (x < 1) sum += 1 - x, x = 1;
        if (n < x) sum += x - n, x = n;
        if (y < 1) sum += 1 - y, y = 1;
        if (2 < y) sum += y - 2, y = 2;
        ++cnt[y][x];
    }

    for (int i = 1; i <= n; ++i) {
        --cnt[1][i], --cnt[2][i];

        if (cnt[1][i] > 0 && cnt[2][i] < 0) {
            int mi = min(cnt[1][i], -cnt[2][i]);
            cnt[1][i] -= mi;
            cnt[2][i] += mi;
            sum += mi;
        }
        else if (cnt[1][i] < 0 && cnt[2][i] > 0) {
            int mi = min(-cnt[1][i], cnt[2][i]);
            cnt[1][i] += mi;
            cnt[2][i] -= mi;
            sum += mi;
        }

        cnt[1][i + 1] += cnt[1][i];
        sum += abs(cnt[1][i]);

        cnt[2][i + 1] += cnt[2][i];
        sum += abs(cnt[2][i]);
    }
    cout << sum << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...