oj.uz

Submission #107376

# Submission time Handle Problem Language Result Execution time Memory
107376 2019-04-23T14:11:54 Z tjd229 Land of the Rainbow Gold (APIO17_rainbow) C++11
100 / 100
 1973 ms 146480 KB 
#include "rainbow.h"
#include <stdio.h>
#include <memory.h>
#include <vector>
#include <algorithm>
#define pii pair<int,int>
using namespace std;
const int LEAF = 1 << 18;
const int MEM = 8e6;
//v,ve,he,sq
int st_v[MEM], st_ve[MEM], st_he[MEM], st_sq[MEM];
int l_v[MEM], l_ve[MEM], l_he[MEM], l_sq[MEM];
int r_v[MEM], r_ve[MEM],r_he[MEM], r_sq[MEM];
int rt_v[LEAF], rt_ve[LEAF], rt_he[LEAF], rt_sq[LEAF];
int v, ve, he, sq;
int max_x, max_y, min_x, min_y;
int _R, _C;
inline void unq_sort(vector<pii > &v) {
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end())-v.begin());

}
int make_tree(int pre,int s,int e,int pos,int *st, int *l, int *r, int &cnt) {
	if (pos<s || pos>e) return pre;
	int ix = ++cnt;
	if (s == e) st[ix] = st[pre] + 1;
	else {
		l[ix] = make_tree(l[pre], s, (s + e) >> 1, pos, st, l, r, cnt);
		r[ix] = make_tree(r[pre], 1+( (s + e) >> 1),e, pos, st, l, r, cnt);
		st[ix] = st[l[ix]] + st[r[ix]];
	}
	return ix;
}
void make_tree(vector<pii > &v,int *root,int *st,int *l,int *r,int &cnt) {
	auto it = v.begin();
	for (int y = 1; y <= _R; ++y) {
		if (it != v.end() && y == it->first) {
			int pre = root[y - 1];
			while (it != v.end() && y == it->first) {
				pre = root[y] = make_tree(pre, 0, LEAF - 1, it->second, st, l, r, cnt);
				++it;
			}
		}
		else root[y] = root[y - 1];
	}
}
int range_sum(int ix, int s,int e,int from,int to, int *st, int *l, int *r) {
	if (ix == 0) return 0;
	else if (e < from || to < s) return 0;
	else if (from <= s && e <= to) return st[ix];
	return range_sum(l[ix], s, (s + e) >> 1, from, to, st, l, r)
		+ range_sum(r[ix], 1 + ((s + e) >> 1), e, from, to, st, l, r);
}
int sum(int y1,int x1,int y2,int x2,int *root,int *st, int *l, int *r) {
	if (x2 < x1 || y2 < y1) return 0;

	return range_sum(root[y2], 0, LEAF - 1, x1, x2, st, l, r)
		- range_sum(root[y1 - 1], 0, LEAF - 1, x1, x2, st, l, r);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
	_R = R; _C = C;
	v = ve = he = sq = 0;
	max_x = max_y = 0; min_x = C+1; min_y = R+1;
	vector<pii > vv,vve,vhe,vsq;
	vsq.push_back({sr,sc});//y,x
	for (int i = 0; i < M; ++i) {
		switch (S[i]) {
		case 'N':
			--sr; break;
		case 'E':
			++sc; break;
		case 'S':
			++sr; break;
		case 'W':
			--sc; break;
		}
		vsq.push_back({ sr,sc });
	}
	unq_sort(vsq);
	for (auto p : vsq) {
		vv.push_back(p); vv.push_back({ p.first,p.second + 1 });
		vv.push_back({ p.first + 1,p.second}); vv.push_back({ p.first+1,p.second + 1 });
		vve.push_back(p); vve.push_back({ p.first,p.second + 1 });
		vhe.push_back(p); vhe.push_back({ p.first+1,p.second });
		min_x = min(min_x, p.second); max_x = max(max_x, p.second + 1);
		min_y = min(min_y, p.first); max_y = max(max_y, p.first + 1);
	}
	_R = max(_R, max_y); _C = max(_C, max_x);
	unq_sort(vv); unq_sort(vve); unq_sort(vhe);
	make_tree(vsq, rt_sq, st_sq, l_sq, r_sq, sq);

	make_tree(vv, rt_v, st_v, l_v, r_v, v);
	make_tree(vve, rt_ve, st_ve, l_ve, r_ve, ve);
	make_tree(vhe, rt_he, st_he, l_he, r_he, he);
}
int colour(int ar, int ac, int br, int bc) {
	//return 0;
	int v = br + br + 4 - ar - ar + bc + bc + 4 - ac - ac - 4;
	int e = v;
	v += sum(ar + 1, ac + 1, br, bc,rt_v,st_v,l_v,r_v);
	e += sum(ar, ac+1, br, bc, rt_ve, st_ve, l_ve, r_ve)
		+ sum(ar+1, ac, br, bc, rt_he, st_he, l_he, r_he);
	int sq = sum(ar,ac,br,bc,rt_sq,st_sq,l_sq,r_sq);
	//printf("%d,%d,%d\n",v,e,sq);
	//printf("%d,%d,%d,%d\n",min_x,max_x,min_y,max_y);
	int f = 2 + e - v - sq;
	if (ac < min_x && ar < min_y && max_x <= bc && max_y <= br) ++f;
    return f-1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 7 ms 1664 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 9 ms 1920 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 9 ms 896 KB Output is correct
12 Correct 7 ms 1280 KB Output is correct
13 Correct 12 ms 2304 KB Output is correct
14 Correct 11 ms 2736 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 537 ms 86072 KB Output is correct
4 Correct 908 ms 143068 KB Output is correct
5 Correct 945 ms 142036 KB Output is correct
6 Correct 591 ms 110820 KB Output is correct
7 Correct 952 ms 108516 KB Output is correct
8 Correct 89 ms 4172 KB Output is correct
9 Correct 1010 ms 143028 KB Output is correct
10 Correct 949 ms 142008 KB Output is correct
11 Correct 695 ms 110868 KB Output is correct
12 Correct 446 ms 133204 KB Output is correct
13 Correct 451 ms 143204 KB Output is correct
14 Correct 554 ms 142180 KB Output is correct
15 Correct 410 ms 111076 KB Output is correct
16 Correct 523 ms 102244 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 417 ms 146196 KB Output is correct
3 Correct 310 ms 146264 KB Output is correct
4 Correct 295 ms 146268 KB Output is correct
5 Correct 303 ms 111460 KB Output is correct
6 Correct 73 ms 31720 KB Output is correct
7 Correct 136 ms 58660 KB Output is correct
8 Correct 381 ms 128220 KB Output is correct
9 Correct 331 ms 114204 KB Output is correct
10 Correct 84 ms 30876 KB Output is correct
11 Correct 159 ms 72704 KB Output is correct
12 Correct 305 ms 146276 KB Output is correct
13 Correct 248 ms 146188 KB Output is correct
14 Correct 302 ms 146276 KB Output is correct
15 Correct 211 ms 111512 KB Output is correct
16 Correct 60 ms 26600 KB Output is correct
17 Correct 115 ms 58644 KB Output is correct
18 Correct 335 ms 146392 KB Output is correct
19 Correct 277 ms 146120 KB Output is correct
20 Correct 298 ms 146148 KB Output is correct
21 Correct 335 ms 128100 KB Output is correct
22 Correct 329 ms 114276 KB Output is correct
23 Correct 66 ms 30956 KB Output is correct
24 Correct 171 ms 72680 KB Output is correct
25 Correct 372 ms 146248 KB Output is correct
26 Correct 259 ms 146148 KB Output is correct
27 Correct 256 ms 146148 KB Output is correct
28 Correct 241 ms 111460 KB Output is correct
29 Correct 62 ms 26600 KB Output is correct
30 Correct 136 ms 58724 KB Output is correct
31 Correct 331 ms 146184 KB Output is correct
32 Correct 337 ms 146272 KB Output is correct
33 Correct 322 ms 146136 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 7 ms 1664 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 9 ms 1920 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 9 ms 896 KB Output is correct
12 Correct 7 ms 1280 KB Output is correct
13 Correct 12 ms 2304 KB Output is correct
14 Correct 11 ms 2736 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 1481 ms 73404 KB Output is correct
19 Correct 373 ms 7120 KB Output is correct
20 Correct 244 ms 4480 KB Output is correct
21 Correct 290 ms 5112 KB Output is correct
22 Correct 384 ms 5756 KB Output is correct
23 Correct 406 ms 6712 KB Output is correct
24 Correct 287 ms 4856 KB Output is correct
25 Correct 311 ms 5416 KB Output is correct
26 Correct 389 ms 5944 KB Output is correct
27 Correct 500 ms 60232 KB Output is correct
28 Correct 316 ms 31648 KB Output is correct
29 Correct 400 ms 55528 KB Output is correct
30 Correct 984 ms 143324 KB Output is correct
31 Correct 7 ms 512 KB Output is correct
32 Correct 1189 ms 60904 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 7 ms 1664 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 9 ms 1920 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 9 ms 896 KB Output is correct
12 Correct 7 ms 1280 KB Output is correct
13 Correct 12 ms 2304 KB Output is correct
14 Correct 11 ms 2736 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 1481 ms 73404 KB Output is correct
19 Correct 373 ms 7120 KB Output is correct
20 Correct 244 ms 4480 KB Output is correct
21 Correct 290 ms 5112 KB Output is correct
22 Correct 384 ms 5756 KB Output is correct
23 Correct 406 ms 6712 KB Output is correct
24 Correct 287 ms 4856 KB Output is correct
25 Correct 311 ms 5416 KB Output is correct
26 Correct 389 ms 5944 KB Output is correct
27 Correct 500 ms 60232 KB Output is correct
28 Correct 316 ms 31648 KB Output is correct
29 Correct 400 ms 55528 KB Output is correct
30 Correct 984 ms 143324 KB Output is correct
31 Correct 7 ms 512 KB Output is correct
32 Correct 1189 ms 60904 KB Output is correct
33 Correct 417 ms 146196 KB Output is correct
34 Correct 310 ms 146264 KB Output is correct
35 Correct 295 ms 146268 KB Output is correct
36 Correct 303 ms 111460 KB Output is correct
37 Correct 73 ms 31720 KB Output is correct
38 Correct 136 ms 58660 KB Output is correct
39 Correct 381 ms 128220 KB Output is correct
40 Correct 331 ms 114204 KB Output is correct
41 Correct 84 ms 30876 KB Output is correct
42 Correct 159 ms 72704 KB Output is correct
43 Correct 305 ms 146276 KB Output is correct
44 Correct 248 ms 146188 KB Output is correct
45 Correct 302 ms 146276 KB Output is correct
46 Correct 211 ms 111512 KB Output is correct
47 Correct 60 ms 26600 KB Output is correct
48 Correct 115 ms 58644 KB Output is correct
49 Correct 335 ms 146392 KB Output is correct
50 Correct 277 ms 146120 KB Output is correct
51 Correct 298 ms 146148 KB Output is correct
52 Correct 335 ms 128100 KB Output is correct
53 Correct 329 ms 114276 KB Output is correct
54 Correct 66 ms 30956 KB Output is correct
55 Correct 171 ms 72680 KB Output is correct
56 Correct 372 ms 146248 KB Output is correct
57 Correct 259 ms 146148 KB Output is correct
58 Correct 256 ms 146148 KB Output is correct
59 Correct 241 ms 111460 KB Output is correct
60 Correct 62 ms 26600 KB Output is correct
61 Correct 136 ms 58724 KB Output is correct
62 Correct 331 ms 146184 KB Output is correct
63 Correct 337 ms 146272 KB Output is correct
64 Correct 322 ms 146136 KB Output is correct
65 Correct 1973 ms 128300 KB Output is correct
66 Correct 1940 ms 114404 KB Output is correct
67 Correct 692 ms 32208 KB Output is correct
68 Correct 670 ms 72884 KB Output is correct
69 Correct 819 ms 146340 KB Output is correct
70 Correct 584 ms 146476 KB Output is correct
71 Correct 624 ms 146420 KB Output is correct
72 Correct 475 ms 111652 KB Output is correct
73 Correct 224 ms 28704 KB Output is correct
74 Correct 342 ms 58980 KB Output is correct
75 Correct 630 ms 146368 KB Output is correct
76 Correct 872 ms 146480 KB Output is correct
77 Correct 789 ms 146208 KB Output is correct
78 Correct 537 ms 86072 KB Output is correct
79 Correct 908 ms 143068 KB Output is correct
80 Correct 945 ms 142036 KB Output is correct
81 Correct 591 ms 110820 KB Output is correct
82 Correct 952 ms 108516 KB Output is correct
83 Correct 89 ms 4172 KB Output is correct
84 Correct 1010 ms 143028 KB Output is correct
85 Correct 949 ms 142008 KB Output is correct
86 Correct 695 ms 110868 KB Output is correct
87 Correct 446 ms 133204 KB Output is correct
88 Correct 451 ms 143204 KB Output is correct
89 Correct 554 ms 142180 KB Output is correct
90 Correct 410 ms 111076 KB Output is correct
91 Correct 523 ms 102244 KB Output is correct