제출 #380624

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380624		rainboy	무지개나라 (APIO17_rainbow)	C11	100 / 100	1155 ms	153060 KiB

rainbow

/* upsolve using persistent segment tree */
#include "rainbow.h"
#include <stdio.h>
#include <stdlib.h>

#define N	200000
#define M	200000
#define L	100000
#define LG	18	/* LG = ceil(log2(M)) */
#define N_	((L + 1) * 9 * (LG + 1))

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

int cnt[1 + N_], ll[1 + N_], rr[1 + N_];

int update(int t, int l, int r, int i) {
	static int _ = 1;
	int t_ = _++;

	cnt[t_] = cnt[t] + 1;
	if (r - l > 1) {
		int m = (l + r) / 2;

		if (i < m)
			ll[t_] = update(ll[t], l, m, i), rr[t_] = rr[t];
		else
			ll[t_] = ll[t], rr[t_] = update(rr[t], m, r, i);
	}
	return t_++;
}

int query_(int t, int l, int r, int ql, int qr) {
	int m;

	if (qr <= l || r <= ql || !t)
		return 0;
	if (ql <= l && r <= qr)
		return cnt[t];
	m = (l + r) / 2;
	return query_(ll[t], l, m, ql, qr) + query_(rr[t], m, r, ql, qr);
}

int *jjj[N], kk[N], n, m;

void build(int *tt, int *ii, int *jj, int l) {
	static char used[M];
	int h, i, j, t;

	for (h = 0; h < l; h++)
		if (ii[h] < n)
			kk[ii[h]]++;
	for (i = 0; i < n; i++)
		jjj[i] = (int *) malloc(kk[i] * sizeof *jjj[i]), kk[i] = 0;
	for (h = 0; h < l; h++) {
		i = ii[h], j = jj[h];
		if (i < n && j < m)
			jjj[i][kk[i]++] = j;
	}
	for (i = 0, t = 0; i < n; i++) {
		for (h = 0; h < kk[i]; h++) {
			j = jjj[i][h];
			if (!used[j])
				used[j] = 1, t = update(t, 0, m, j);
		}
		for (h = 0; h < kk[i]; h++) {
			j = jjj[i][h];
			used[j] = 0;
		}
		tt[i] = t;
	}
	for (i = 0; i < n; i++)
		free(jjj[i]);
}

int ttv[N], tte1[N], tte2[N], ttf[N], 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;

	n = n_, m = m_, 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++;
	build(ttv, ii, jj, l);
	for (h = 0; h < l; h++)
		ii[l + h] = ii[h], jj[l + h] = jj[h] + 1;
	build(tte1, ii, jj, l * 2);
	for (h = 0; h < l; h++)
		ii[l + h] = ii[h] + 1, jj[l + h] = jj[h];
	build(tte2, 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(ttf, ii, jj, l * 4);
}

long long query(int *tt, int il, int ir, int jl, int jr) {
	return il > ir || jl > jr ? 0 : (long long) (ir - il + 1) * (jr - jl + 1) - (query_(tt[ir], 0, m, jl, jr + 1) - (il == 0 ? 0 : query_(tt[il - 1], 0, m, jl, jr + 1)));
}

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

	il--, jl--, ir--, jr--;
	v = query(ttv, il, ir, jl, jr);
	e = query(tte1, il, ir, jl + 1, jr) + query(tte2, il + 1, ir, jl, jr);
	f = query(ttf, 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: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26