Submission #207125

#TimeUsernameProblemLanguageResultExecution timeMemory
207125SaboonCoin Collecting (JOI19_ho_t4)C++14
100 / 100
79 ms5752 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
 
const int maxn = 100000 + 10;
const int inf = 1e9;

int dw[maxn], up[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	ll answer = 0;
	for (int i = 1; i <= 2*n; i++){
		int x, y;
		cin >> x >> y;
		if (x < 1)
			answer += (1 - x), x = 1;
		if (n < x)
			answer += (x - n), x = n;
		if (y < 1)
			answer += (1 - y), y = 1;
		if (2 < y)
			answer += (y - 2), y = 2;
		if (y == 1)
			dw[x] ++;
		else
			up[x] ++;
	}
	int lo = 1, hi = 1;
	for (int i = 1; i <= n; i++){
		while (lo <= i and dw[i] > 0){
			dw[i] --;
			answer += (i - lo);
			lo ++;
		}
		while (hi <= i and up[i] > 0){
			up[i] --;
			answer += (i - hi);
			hi ++;
		}
		while (hi <= i and dw[i] > 0){
			dw[i] --;
			answer += (i - hi + 1);
			hi ++;
		}
		while (lo <= i and up[i] > 0){
			up[i] --;
			answer += (i - lo + 1);
			lo ++;
		}
		answer += up[i] + dw[i];
		up[i + 1] += up[i];
		dw[i + 1] += dw[i];
	}
	cout << answer << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...