Submission #100573

#	Time	Username	Problem	Language	Result	Execution time	Memory
100573		ainta	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	94 ms	8028 KiB

joi2019_ho_t4

#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 201000
using namespace std;
long long res;
struct point {
	int x, y;
}w[N_];
int C[N_][2], n, S[N_], T[N_];
void Right(int b, int e) {
	int i;
	int s1 = 0, s2 = 0;
	for (i = b; i <= e; i++) {
		s1 += C[i][0];
		s2 += C[i][1];
		if (i == e && s1 + s2 == 1) {
			C[i][0] = s1;
			C[i][1] = s2;
			continue;
		}
		if (s1 == 0) {
			C[i][0] = C[i][1] = 1;
			s2 -= 2;
			res++;
		}
		else if (s2 == 0) {
			C[i][0] = C[i][1] = 1;
			s1 -= 2;
			res++;
		}
		else {
			C[i][0] = C[i][1] = 1;
			s1--, s2--;
		}
	}
}
void Go(int b, int e, int pv) {
	int i;
	int s1 = 0, s2 = 0;
	for (i = b; i < pv; i++) {
		s1 += C[i][0];
		s2 += C[i][1];
		if (s1 > i-b+1) {
			int t = s1 - (i - b + 1);
			C[i][0] -= t;
			C[i][1] += t;
			res += t;
			s1 -= t;
			s2 += t;
		}
		if(s2 > i-b+1){
			int t = s2 - (i - b + 1);
			C[i][0] += t;
			C[i][1] -= t;
			res += t;
			s1 += t;
			s2 -= t;
		}
	}
	s1 = pv - b - s1;
	s2 = pv - b - s2;
	if (s1 > C[pv][0]) {
		int t = s1 - C[pv][0];
		C[pv][0] += t;
		C[pv][1] -= t;
		res += t;
	}
	if (s2 > C[pv][1]) {
		int t = s2 - C[pv][1];
		C[pv][0] -= t;
		C[pv][1] += t;
		res += t;
	}
	C[pv][0] -= s1;
	C[pv][1] -= s2;
	for (i = b; i < pv; i++) {
		C[i][0] = C[i][1] = 1;
	}
	Right(pv, e);
}
int main() {
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= n * 2; i++) {
		scanf("%d%d", &w[i].x, &w[i].y);
		if (w[i].x < 1) {
			res += 1 - w[i].x;
			w[i].x = 1;
		}
		if (w[i].x > n) {
			res += w[i].x - n;
			w[i].x = n;
		}
		if (w[i].y < 1) {
			res += 1 - w[i].y;
			w[i].y = 1;
		}
		if (w[i].y > 2) {
			res += w[i].y - 2;
			w[i].y = 2;
		}
		C[w[i].x][w[i].y - 1]++;
	}
	for (i = 1; i <= n; i++) {
		S[i] = S[i - 1] + C[i][0] + C[i][1];
		T[i] = S[i] - i * 2;
	}
	for (i = 1; i < n; i++) {
		res += abs(T[i]);
	}
	for (i = 1; i < n; i++) {
		if (T[i] == 0)continue;
		if (T[i] > 0) {
			for (j = i; j < n; j++)if (T[j] <= 0)break;
			Right(i, j);
			i = j - 1;
			continue;
		}
		else {
			for (j = i; j < n; j++)if (T[j] >= 0)break;
			int pv = j;
			if (T[pv] > 0) {
				for (j = pv; j < n; j++)if (T[j] <= 0)break;
				Go(i, j, pv);
				i = j - 1;
			}
			else {
				Go(i, pv, pv);
				i = pv - 1;
			}
		}
	}
	for (i = 1; i <= n; i++) {
		res += abs(C[i][0] - C[i][1]) / 2;
	}
	printf("%lld\n", res);
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
joi2019_ho_t4.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &w[i].x, &w[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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