Submission #379989

#	Time	Username	Problem	Language	Result	Execution time	Memory
379989		rainboy	Land of the Rainbow Gold (APIO17_rainbow)	C11	50 / 100	1275 ms	1048576 KiB

rainbow

#include "rainbow.h"
#include <stdlib.h>

#define N	100000
#define L	100000
#define N_	(1 << 17)	/* N_ = pow2(ceil(log2(N))) */

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

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

void sort(int *aa, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, a = aa[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa[j] == a)
				j++;
			else if (aa[j] < a) {
				tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
			}
		sort(aa, l, i);
		l = k;
	}
}

void merge(int *aa, int n, int *bb, int m, int *cc) {
	int i, j, k;

	i = 0, j = 0, k = 0;
	while (i < n && j < m)
		cc[k++] = aa[i] < bb[j] ? aa[i++] : bb[j++];
	while (i < n)
		cc[k++] = aa[i++];
	while (j < m)
		cc[k++] = bb[j++];
}

int n_;

void build(int **st, int *kk, int *ii, int *jj, int l) {
	int h, i, j;

	for (h = 0; h < l; h++)
		if (ii[h] < n_)
			kk[n_ + ii[h]]++;
	for (i = 0; i < n_; i++)
		st[n_ + i] = (int *) malloc(kk[n_ + i] * sizeof *st[n_ + i]), kk[n_ + i] = 0;
	for (h = 0; h < l; h++) {
		i = ii[h], j = jj[h];
		if (i < n_)
			st[n_ + i][kk[n_ + i]++] = j;
	}
	for (i = n_; i < n_ * 2; i++) {
		int k;

		sort(st[i], 0, kk[i]);
		k = 0;
		for (h = 0; h < kk[i]; h++)
			if (k == 0 || st[i][h] != st[i][k - 1])
				st[i][k++] = st[i][h];
		kk[i] = k;
	}
	for (i = n_ - 1; i > 0; i--) {
		int l = i << 1, r = l | 1;

		st[i] = (int *) malloc((kk[i] = kk[l] + kk[r]) * sizeof *st[i]);
		merge(st[l], kk[l], st[r], kk[r], st[i]);
	}
}

int *stv[N_ * 2], kkv[N_ * 2], *ste1[N_ * 2], kke1[N_ * 2], *ste2[N_ * 2], kke2[N_ * 2], *stf[N_ * 2], kkf[N_ * 2], imin, imax, jmin, jmax;

void init(int n, int m, int i_, int j_, int l, char *dd) {
	static int ii[(L + 1) * 4], jj[(L + 1) * 4];
	int h;

	i_--, j_--;
	imin = imax = i_, jmin = jmax = j_;
	ii[0] = i_, jj[0] = j_;
	for (h = 0; h < l; h++) {
		if (dd[h] == 'N')
			i_--;
		else if (dd[h] == 'S')
			i_++;
		else if (dd[h] == 'W')
			j_--;
		else
			j_++;
		imin = min(imin, i_), imax = max(imax, i_);
		jmin = min(jmin, j_), jmax = max(jmax, j_);
		ii[h + 1] = i_, jj[h + 1] = j_;
	}
	l++;
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	build(stv, kkv, ii, jj, l);
	for (h = 0; h < l; h++)
		ii[l + h] = ii[h], jj[l + h] = jj[h] + 1;
	build(ste1, kke1, ii, jj, l * 2);
	for (h = 0; h < l; h++)
		ii[l + h] = ii[h] + 1, jj[l + h] = jj[h];
	build(ste2, kke2, ii, jj, l * 2);
	for (h = 0; h < l; h++) {
		ii[l + h] = ii[h], jj[l + h] = jj[h] + 1;
		ii[l + l + h] = ii[h] + 1, jj[l + l + h] = jj[h];
		ii[l + l + l + h] = ii[h] + 1, jj[l + l + l + h] = jj[h] + 1;
	}
	build(stf, kkf, ii, jj, l * 4);
}

int query_(int *aa, int n, int a) {
	int lower = -1, upper = n;

	while (upper - lower > 1) {
		int i = (lower + upper) / 2;

		if (aa[i] <= a)
			lower = i;
		else
			upper = i;
	}
	return upper;
}

long long query(int **st, int *kk, int il, int ir, int jl, int jr) {
	long long ans;

	if (il > ir || jl > jr)
		return 0;
	ans = (long long) (ir - il + 1) * (jr - jl + 1);
	for (il += n_, ir += n_; il <= ir; il >>= 1, ir >>= 1) {
		if ((il & 1) == 1)
			ans -= query_(st[il], kk[il], jr) - query_(st[il], kk[il], jl - 1), il++;
		if ((ir & 1) == 0)
			ans -= query_(st[ir], kk[ir], jr) - query_(st[ir], kk[ir], jl - 1), ir--;
	}
	return ans;
}

int colour(int il, int jl, int ir, int jr) {
	long long v, e, f;

	il--, jl--, ir--, jr--;
	v = query(stv, kkv, il, ir, jl, jr);
	e = query(ste1, kke1, il, ir, jl + 1, jr) + query(ste2, kke2, il + 1, ir, jl, jr);
	f = query(stf, kkf, il + 1, ir, jl + 1, jr);
	if (il < imin && imax < ir && jl < jmin && jmax < jr)
		f++;
	return v - e + f;
}

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 27 / 27
• Subtask 5: 0 / 26