Submission #703274

#	Time	Username	Problem	Language	Result	Execution time	Memory
703274		rainboy	Colouring a rectangle (eJOI19_colouring)	C11	100 / 100	155 ms	47600 KiB

colouring

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	200000
#define M	200000
#define N_	(N + M - 1)

int max(int a, int b) { return a > b ? a : b; }

int *el[N_], *ea[N_], eo[N_];

void append(int r, int l, int a) {
	int o = eo[r]++;

	if (o >= 2 && (o & o - 1) == 0) {
		el[r] = (int *) realloc(el[r], o * 2 * sizeof *el[r]);
		ea[r] = (int *) realloc(ea[r], o * 2 * sizeof *ea[r]);
	}
	el[r][o] = l, ea[r][o] = a;
}

int aa[N_], bb[N_];
int ds[N_], rr[N_]; char marked[N_]; int n, m, n_;

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j, rr[j] = max(rr[j], rr[i]);
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, rr[i] = max(rr[i], rr[j]);
	}
}

void mark(int i) {
	marked[i] = 1;
	if (i >= 2 && marked[i - 2])
		join(i - 2, i);
	if (i + 2 < n_ && marked[i + 2])
		join(i, i + 2);
}

int nxt(int i) {
	return !marked[i] ? i : rr[find(i)] + 2;
}

int main() {
	int h, l, r, a, o;
	long long ans;

	scanf("%d%d", &n, &m), n_ = n + m - 1;
	for (h = 0; h < n_; h++)
		scanf("%d", &aa[h]);
	for (h = 0; h < n_; h++)
		scanf("%d", &bb[h]);
	for (r = 0; r < n_; r++) {
		el[r] = (int *) malloc(2 * sizeof *el[r]);
		ea[r] = (int *) malloc(2 * sizeof *ea[r]);
	}
	for (h = 0; h < n_; h++) {
		l = h < m ? m - 1 - h : h - m + 1, r = h < n ? m - 1 + h : n_ - 1 + n - 1 - h;
		append(r, l, aa[h]);
	}
	memset(ds, -1, n_ * sizeof *ds);
	for (h = 0; h < n_; h++)
		rr[h] = h;
	ans = 0;
	for (r = 0; r < n_; r++)
		for (o = eo[r]; o--; ) {
			l = el[r][o], a = ea[r][o];
			h = l;
			while ((h = nxt(h)) <= r)
				if (a >= bb[h])
					a -= bb[h], ans += bb[h], bb[h] = 0, mark(h);
				else {
					bb[h] -= a, ans += a;
					break;
				}
		}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

colouring.c: In function 'append':
colouring.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
colouring.c: In function 'main':
colouring.c:60:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d%d", &n, &m), n_ = n + m - 1;
      |  ^~~~~~~~~~~~~~~~~~~~~
colouring.c:62:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d", &aa[h]);
      |   ^~~~~~~~~~~~~~~~~~~
colouring.c:64:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d", &bb[h]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20