답안 #380624

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380624	2021-03-22T14:58:32 Z	rainboy	무지개나라 (APIO17_rainbow)	C	100 / 100	1155 ms	153060 KB

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.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	492 KB	Output is correct
2	Correct	3 ms	876 KB	Output is correct
3	Correct	2 ms	492 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	3 ms	1004 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	0 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	2 ms	620 KB	Output is correct
12	Correct	4 ms	876 KB	Output is correct
13	Correct	3 ms	1132 KB	Output is correct
14	Correct	4 ms	1388 KB	Output is correct
15	Correct	0 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	329 ms	70100 KB	Output is correct
4	Correct	490 ms	117172 KB	Output is correct
5	Correct	516 ms	115600 KB	Output is correct
6	Correct	347 ms	88504 KB	Output is correct
7	Correct	515 ms	90600 KB	Output is correct
8	Correct	94 ms	7612 KB	Output is correct
9	Correct	537 ms	117684 KB	Output is correct
10	Correct	539 ms	115764 KB	Output is correct
11	Correct	406 ms	88380 KB	Output is correct
12	Correct	213 ms	104796 KB	Output is correct
13	Correct	245 ms	117180 KB	Output is correct
14	Correct	250 ms	115256 KB	Output is correct
15	Correct	218 ms	88508 KB	Output is correct
16	Correct	354 ms	89728 KB	Output is correct

Subtask #3

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	243 ms	149476 KB	Output is correct
3	Correct	218 ms	147000 KB	Output is correct
4	Correct	239 ms	148716 KB	Output is correct
5	Correct	183 ms	114648 KB	Output is correct
6	Correct	92 ms	42476 KB	Output is correct
7	Correct	124 ms	67052 KB	Output is correct
8	Correct	149 ms	92508 KB	Output is correct
9	Correct	134 ms	82560 KB	Output is correct
10	Correct	52 ms	24840 KB	Output is correct
11	Correct	102 ms	59516 KB	Output is correct
12	Correct	241 ms	149476 KB	Output is correct
13	Correct	214 ms	146924 KB	Output is correct
14	Correct	245 ms	148716 KB	Output is correct
15	Correct	184 ms	114520 KB	Output is correct
16	Correct	82 ms	37484 KB	Output is correct
17	Correct	128 ms	67180 KB	Output is correct
18	Correct	222 ms	149484 KB	Output is correct
19	Correct	228 ms	146984 KB	Output is correct
20	Correct	227 ms	147104 KB	Output is correct
21	Correct	150 ms	92408 KB	Output is correct
22	Correct	134 ms	82560 KB	Output is correct
23	Correct	52 ms	24840 KB	Output is correct
24	Correct	103 ms	59516 KB	Output is correct
25	Correct	239 ms	149476 KB	Output is correct
26	Correct	216 ms	146924 KB	Output is correct
27	Correct	241 ms	148716 KB	Output is correct
28	Correct	184 ms	114648 KB	Output is correct
29	Correct	82 ms	37484 KB	Output is correct
30	Correct	129 ms	67180 KB	Output is correct
31	Correct	224 ms	149484 KB	Output is correct
32	Correct	230 ms	146984 KB	Output is correct
33	Correct	229 ms	146984 KB	Output is correct

Subtask #4

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	492 KB	Output is correct
2	Correct	3 ms	876 KB	Output is correct
3	Correct	2 ms	492 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	3 ms	1004 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	0 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	2 ms	620 KB	Output is correct
12	Correct	4 ms	876 KB	Output is correct
13	Correct	3 ms	1132 KB	Output is correct
14	Correct	4 ms	1388 KB	Output is correct
15	Correct	0 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	785 ms	46456 KB	Output is correct
19	Correct	230 ms	5868 KB	Output is correct
20	Correct	146 ms	4076 KB	Output is correct
21	Correct	172 ms	4460 KB	Output is correct
22	Correct	191 ms	4864 KB	Output is correct
23	Correct	225 ms	5612 KB	Output is correct
24	Correct	152 ms	4332 KB	Output is correct
25	Correct	175 ms	4844 KB	Output is correct
26	Correct	191 ms	5100 KB	Output is correct
27	Correct	248 ms	38856 KB	Output is correct
28	Correct	193 ms	24748 KB	Output is correct
29	Correct	224 ms	36424 KB	Output is correct
30	Correct	444 ms	84984 KB	Output is correct
31	Correct	3 ms	492 KB	Output is correct
32	Correct	580 ms	40788 KB	Output is correct

Subtask #5

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	492 KB	Output is correct
2	Correct	3 ms	876 KB	Output is correct
3	Correct	2 ms	492 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	3 ms	1004 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	0 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	2 ms	620 KB	Output is correct
12	Correct	4 ms	876 KB	Output is correct
13	Correct	3 ms	1132 KB	Output is correct
14	Correct	4 ms	1388 KB	Output is correct
15	Correct	0 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	785 ms	46456 KB	Output is correct
19	Correct	230 ms	5868 KB	Output is correct
20	Correct	146 ms	4076 KB	Output is correct
21	Correct	172 ms	4460 KB	Output is correct
22	Correct	191 ms	4864 KB	Output is correct
23	Correct	225 ms	5612 KB	Output is correct
24	Correct	152 ms	4332 KB	Output is correct
25	Correct	175 ms	4844 KB	Output is correct
26	Correct	191 ms	5100 KB	Output is correct
27	Correct	248 ms	38856 KB	Output is correct
28	Correct	193 ms	24748 KB	Output is correct
29	Correct	224 ms	36424 KB	Output is correct
30	Correct	444 ms	84984 KB	Output is correct
31	Correct	3 ms	492 KB	Output is correct
32	Correct	580 ms	40788 KB	Output is correct
33	Correct	243 ms	149476 KB	Output is correct
34	Correct	218 ms	147000 KB	Output is correct
35	Correct	239 ms	148716 KB	Output is correct
36	Correct	183 ms	114648 KB	Output is correct
37	Correct	92 ms	42476 KB	Output is correct
38	Correct	124 ms	67052 KB	Output is correct
39	Correct	149 ms	92508 KB	Output is correct
40	Correct	134 ms	82560 KB	Output is correct
41	Correct	52 ms	24840 KB	Output is correct
42	Correct	102 ms	59516 KB	Output is correct
43	Correct	241 ms	149476 KB	Output is correct
44	Correct	214 ms	146924 KB	Output is correct
45	Correct	245 ms	148716 KB	Output is correct
46	Correct	184 ms	114520 KB	Output is correct
47	Correct	82 ms	37484 KB	Output is correct
48	Correct	128 ms	67180 KB	Output is correct
49	Correct	222 ms	149484 KB	Output is correct
50	Correct	228 ms	146984 KB	Output is correct
51	Correct	227 ms	147104 KB	Output is correct
52	Correct	150 ms	92408 KB	Output is correct
53	Correct	134 ms	82560 KB	Output is correct
54	Correct	52 ms	24840 KB	Output is correct
55	Correct	103 ms	59516 KB	Output is correct
56	Correct	239 ms	149476 KB	Output is correct
57	Correct	216 ms	146924 KB	Output is correct
58	Correct	241 ms	148716 KB	Output is correct
59	Correct	184 ms	114648 KB	Output is correct
60	Correct	82 ms	37484 KB	Output is correct
61	Correct	129 ms	67180 KB	Output is correct
62	Correct	224 ms	149484 KB	Output is correct
63	Correct	230 ms	146984 KB	Output is correct
64	Correct	229 ms	146984 KB	Output is correct
65	Correct	329 ms	70100 KB	Output is correct
66	Correct	490 ms	117172 KB	Output is correct
67	Correct	516 ms	115600 KB	Output is correct
68	Correct	347 ms	88504 KB	Output is correct
69	Correct	515 ms	90600 KB	Output is correct
70	Correct	94 ms	7612 KB	Output is correct
71	Correct	537 ms	117684 KB	Output is correct
72	Correct	539 ms	115764 KB	Output is correct
73	Correct	406 ms	88380 KB	Output is correct
74	Correct	213 ms	104796 KB	Output is correct
75	Correct	245 ms	117180 KB	Output is correct
76	Correct	250 ms	115256 KB	Output is correct
77	Correct	218 ms	88508 KB	Output is correct
78	Correct	354 ms	89728 KB	Output is correct
79	Correct	1130 ms	95140 KB	Output is correct
80	Correct	1155 ms	84952 KB	Output is correct
81	Correct	363 ms	27588 KB	Output is correct
82	Correct	382 ms	61372 KB	Output is correct
83	Correct	608 ms	153060 KB	Output is correct
84	Correct	418 ms	150508 KB	Output is correct
85	Correct	491 ms	152300 KB	Output is correct
86	Correct	387 ms	118232 KB	Output is correct
87	Correct	181 ms	41068 KB	Output is correct
88	Correct	236 ms	70636 KB	Output is correct
89	Correct	341 ms	152940 KB	Output is correct
90	Correct	624 ms	150568 KB	Output is correct
91	Correct	567 ms	150568 KB	Output is correct