제출 #1288881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288881		g4yuhg	Coin Collecting (JOI19_ho_t4)	C++20	100 / 100	40 ms	5132 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
typedef long long ll;
#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK "-"
#define N 200055
#define LOG 17
using namespace std;

const ll inf = 1e18;

bool ghuy4g;

ll n, ans;
pii p[N];

ll a[N][2];
set<ll> s[3];

inline ll cal(ll x, ll y, ll u, ll v) {
	return abs(x - y) + abs(u - v);
}

void solve() {
	ll d1 = 0, d2 = 0;
	for (int i = 1; i <= n; i ++) {
		d1 += a[i][1] - 1;
		d2 += a[i][2] - 1;
		if (d1 > 0 && d2 < 0) {
			ll t = min(d1, -d2);
			ans += t;
			d1 -= t;
			d2 += t;
		}
		else if (d1 < 0 && d2 > 0) {
			ll t = min(-d1, d2);
			ans += t;
			d1 += t;
			d2 -= t;
		}
		ans += abs(d1) + abs(d2);
	}
	cout << ans;
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for (int i = 1; i <= n * 2; i ++) {
    	cin >> p[i].fi >> p[i].se;
    	ll x = 0, y = 0;
    	if (p[i].se == 1 || p[i].se == 2) {
    		if (p[i].fi < 1) {
    			x = 1, y = p[i].se;
    		}
    		else if (p[i].fi > n) {
    			x = n, y = p[i].se;
    		}
    		else {
    			x = p[i].fi, y = p[i].se;
    		}
    	}
    	else if (p[i].se < 1) {
    		if (p[i].fi < 1) {
    			x = 1, y = 1;
    		}
    		else if (p[i].fi > n) {
    			x = n, y = 1;
    		}
    		else {
    			x = p[i].fi, y = 1;
    		}
    	}
    	else if (p[i].se > 2) {
    		if (p[i].fi < 1) {
    			x = 1, y = 2;
    		}
    		else if (p[i].fi > n) {
    			x = n, y = 2;
    		}
    		else {
    			x = p[i].fi, y = 2;
    		}
    	}
    	a[x][y] ++ ;
    	ans += abs(x - p[i].fi) + abs(y - p[i].se);
    	
    }
    solve();
    
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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