제출 #873122

#제출 시각아이디문제언어결과실행 시간메모리
873122hct_2so1Coin Collecting (JOI19_ho_t4)C++17
100 / 100
40 ms7760 KiB
#include <bits/stdc++.h>
 
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define F first
#define S second
#define pii(x, y) make_pair(x, y)
#define __builtin_popcount __builtin_popcountll
#define __builtin_ctz __builtin_ctzll
#define __builtin_clz __builtin_clzll
#define lg(x) (63 - __builtin_clz(x))
 
template <class X, class Y>
    bool minimize(X &x, const Y &y)
    {
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }
 
template <class X, class Y>
    bool maximize(X &x, const Y &y)
    {
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
 
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 6e5;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll oo = 2e18;
const double eps = 1e-1;
 
int n, c[3][N];
pair<int, int> a[2 * N];
 
void Input(void)
{
    cin >> n;
    for (int i = 1; i <= 2 * n; i ++) cin >> a[i].S >> a[i].F;
}
 
void solve(void)
{
    ll ans = 0;
    for (int i = 1; i <= 2 * n; i ++)
    {
        if (a[i].F < 1) ans += 1 - a[i].F, a[i].F = 1;
        if (a[i].F > 2) ans += a[i].F - 2, a[i].F = 2;
        if (a[i].S < 1) ans += 1 - a[i].S, a[i].S = 1;
        if (a[i].S > n) ans += a[i].S - n, a[i].S = n;
        c[a[i].F][a[i].S] ++;
    }
    int row[] = {0, 0, 0};
    for (int i = 1; i <= n; i ++)
    {
        c[1][i] --, c[2][i] --;
        row[1] += c[1][i];
        row[2] += c[2][i];
        if (row[1] < 0 && row[2] > 0)
        {
            int k = min(-row[1], row[2]);
            ans += k;
            row[1] += k;
            row[2] -= k;
        }
        else
            if (row[1] > 0 && row[2] < 0)
            {
                int k = min(row[1], -row[2]);
                ans += k;
                row[1] -= k;
                row[2] += k;
            }
        ans += abs(row[1]) + abs(row[2]);
    }
    cout << ans;
}
 
int main()
{
    std::ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("CLASSROOM.inp", "r", stdin);
//    freopen("CLASSROOM.out", "w", stdout);
    int test = 1;
    //cin >> test;
    while (test --)
    {
        Input();
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...