Submission #538591

#TimeUsernameProblemLanguageResultExecution timeMemory
538591Haruto810198Coin Collecting (JOI19_ho_t4)C++17
100 / 100
62 ms6468 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define double long double
 
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
 
#define vi vector<int>
#define pii pair<int, int>
 
#define F first
#define S second
 
#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 100010;

int n;
int cnt[3][MAX];
int res;

signed main(){
	
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	cin>>n;
	
	FOR(i, 1, 2, 1){
		FOR(j, 1, n, 1){
			cnt[i][j]--;
		}
	}

	FOR(i, 1, 2*n, 1){
		int x, y;
		cin>>x>>y;
		
		if(x < 1){
			res += 1-x;
			x = 1;
		}
		if(x > n){
			res += x-n;
			x = n;
		}

		if(y < 1){
			res += 1-y;
			y = 1;
		}
		if(y > 2){
			res += y-2;
			y = 2;
		}

		cnt[y][x]++;
	}

	FOR(i, 1, n, 1){
		
		int d;
		if(cnt[1][i] > 0 and cnt[2][i] < 0){
			d = min(cnt[1][i], -cnt[2][i]);
			cnt[1][i] -= d;
			cnt[2][i] += d;
			res += d;
		}

		if(cnt[1][i] < 0 and cnt[2][i] > 0){
			d = min(-cnt[1][i], cnt[2][i]);
			cnt[1][i] += d;
			cnt[2][i] -= d;
			res += d;
		}
		
		cnt[1][i+1] += cnt[1][i];
		cnt[2][i+1] += cnt[2][i];
		res += abs(cnt[1][i]) + abs(cnt[2][i]);
		cnt[1][i] = 0;
		cnt[2][i] = 0;
		
	}

	cout<<res<<'\n';
	
	return 0;
	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...