oj.uz

Submission #101737

# Submission time Handle Problem Language Result Execution time Memory
101737 2019-03-19T16:57:57 Z Bruteforceman Land of the Rainbow Gold (APIO17_rainbow) C++11
100 / 100
 1713 ms 149976 KB 
#include "rainbow.h"
#include "bits/stdc++.h"
using namespace std;

int N, M;
typedef pair <int, int> pii;

struct Container {
	vector <int> t[200010 * 4];
	void insert(int x, int y, int c, int b, int e) {
		if(b == e) {
			t[c].emplace_back(y);
			return ;
		}
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		if(x <= m) insert(x, y, l, b, m);
		else insert(x, y, r, m + 1, e);
	}
	void build(int c, int b, int e) {
		if(b == e) {
			sort(t[c].begin(), t[c].end());
			return ;
		}
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		build(l, b, m);
		build(r, m + 1, e);
		merge(t[l].begin(), t[l].end(), t[r].begin(), t[r].end(), back_inserter(t[c]));
	}
	int count(int x, int y, int p, int q, int c, int b, int e) {
		if(x <= b && e <= y) {
			return upper_bound(t[c].begin(), t[c].end(), q) - lower_bound(t[c].begin(), t[c].end(), p);
		}
		if(y < b || e < x) return 0;
		int l = c << 1;
		int r = l + 1;
		int m = (b + e) >> 1;
		return count(x, y, p, q, l, b, m) + count(x, y, p, q, r, m + 1, e);
	}
	int count(int x, int y, int p, int q) {
		if(x > y || p > q) return 0;
		return count(x, y, p, q, 1, 1, N);
	}
	void insert(int x, int y) {
		insert(x, y, 1, 1, N);
	}
	void build() {
		build(1, 1, N);
	}
} E1, E2, V, F;
int lx, rx, ly, ry;

void init(int R, int C, int sr, int sc, int len, char *S) {
	N = R;
	M = C;
	vector <pii> u;
	u.emplace_back(sr, sc);
	// int len = strlen();
	for(int i = 0; i < len; i++) {
		if(S[i] == 'N') --sr;
		else if (S[i] == 'S') ++sr;
		else if (S[i] == 'W') --sc;
		else ++sc;  
		u.emplace_back(sr, sc);
	}
	lx = N, ly = M;
	rx = 1, ry = 1;
	for(auto i : u) {
		lx = min(lx, i.first);
		ly = min(ly, i.second);
		rx = max(rx, i.first);
		ry = max(ry, i.second);
	}	
	set <pii> s;
	for(auto i : u) {
		s.emplace(i.first, i.second);
		s.emplace(i.first - 1, i.second);
		s.emplace(i.first, i.second - 1);
		s.emplace(i.first - 1, i.second - 1);
	}
	for(auto i : s) {
		if(0 < i.first && 0 < i.second) {
			F.insert(i.first, i.second);
		}
	}
	s.clear();
	
	for(auto i : u) {
		s.emplace(i.first - 1, i.second);
		s.emplace(i.first, i.second);
	}
	for(auto i : s) {
		if(0 < i.first && 0 < i.second) {
			E1.insert(i.first, i.second);
		}
	}
	s.clear();
	
	for(auto i : u) {
		s.emplace(i.first, i.second - 1);
		s.emplace(i.first, i.second);
	}
	for(auto i : s) {
		if(0 < i.first && 0 < i.second) {
			E2.insert(i.first, i.second);
		}
	}
	s.clear();
	
	for(auto i : u) {
		s.emplace(i.first, i.second);
	}
	for(auto i : s) {
		V.insert(i.first, i.second);
	}
	s.clear();

	F.build();
	V.build();
	E1.build();
	E2.build();
}

int colour(int ar, int ac, int br, int bc) {
	long long cnt = 0;
	int row = br - ar + 1;
	int col = bc - ac + 1;

	long long e = 0;
	e += 1LL * (row - 1) * col;
	e += 1LL * row * (col - 1);
	e -= E1.count(ar, br - 1, ac, bc);
	e -= E2.count(ar, br, ac, bc - 1);

	long long v = 0;   
	v += 1LL * row * col;
	v -= V.count(ar, br, ac, bc);

	long long f = 1;
	f += 1LL * (row - 1) * (col - 1);
	f -= F.count(ar, br - 1, ac, bc - 1);
	if(ar < lx && rx < br) {
		if(ac < ly && ry < bc) {
			f += 1;
		}
	}
	cnt = v - e + f - 1;
    return cnt;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 75512 KB Output is correct
2 Correct 75 ms 75768 KB Output is correct
3 Correct 71 ms 75512 KB Output is correct
4 Correct 74 ms 75640 KB Output is correct
5 Correct 77 ms 75692 KB Output is correct
6 Correct 66 ms 75412 KB Output is correct
7 Correct 65 ms 75384 KB Output is correct
8 Correct 67 ms 75512 KB Output is correct
9 Correct 67 ms 75512 KB Output is correct
10 Correct 71 ms 75512 KB Output is correct
11 Correct 73 ms 75644 KB Output is correct
12 Correct 71 ms 75640 KB Output is correct
13 Correct 72 ms 75768 KB Output is correct
14 Correct 77 ms 75896 KB Output is correct
15 Correct 76 ms 75484 KB Output is correct
16 Correct 72 ms 75640 KB Output is correct
17 Correct 68 ms 75428 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 75640 KB Output is correct
2 Correct 68 ms 75428 KB Output is correct
3 Correct 338 ms 82828 KB Output is correct
4 Correct 559 ms 88280 KB Output is correct
5 Correct 415 ms 88044 KB Output is correct
6 Correct 364 ms 84840 KB Output is correct
7 Correct 471 ms 85004 KB Output is correct
8 Correct 165 ms 76784 KB Output is correct
9 Correct 376 ms 88196 KB Output is correct
10 Correct 385 ms 88012 KB Output is correct
11 Correct 371 ms 84952 KB Output is correct
12 Correct 408 ms 86844 KB Output is correct
13 Correct 384 ms 88112 KB Output is correct
14 Correct 419 ms 88040 KB Output is correct
15 Correct 321 ms 85028 KB Output is correct
16 Correct 355 ms 84504 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 75484 KB Output is correct
2 Correct 436 ms 122732 KB Output is correct
3 Correct 590 ms 147180 KB Output is correct
4 Correct 529 ms 141044 KB Output is correct
5 Correct 438 ms 123536 KB Output is correct
6 Correct 187 ms 86508 KB Output is correct
7 Correct 261 ms 95980 KB Output is correct
8 Correct 336 ms 87016 KB Output is correct
9 Correct 336 ms 86892 KB Output is correct
10 Correct 186 ms 85600 KB Output is correct
11 Correct 365 ms 99948 KB Output is correct
12 Correct 445 ms 122856 KB Output is correct
13 Correct 659 ms 147020 KB Output is correct
14 Correct 494 ms 141232 KB Output is correct
15 Correct 407 ms 123628 KB Output is correct
16 Correct 195 ms 84328 KB Output is correct
17 Correct 254 ms 96336 KB Output is correct
18 Correct 535 ms 128360 KB Output is correct
19 Correct 502 ms 127080 KB Output is correct
20 Correct 471 ms 127084 KB Output is correct
21 Correct 339 ms 86972 KB Output is correct
22 Correct 335 ms 86892 KB Output is correct
23 Correct 158 ms 85488 KB Output is correct
24 Correct 340 ms 99936 KB Output is correct
25 Correct 481 ms 122732 KB Output is correct
26 Correct 545 ms 147048 KB Output is correct
27 Correct 550 ms 141224 KB Output is correct
28 Correct 466 ms 123704 KB Output is correct
29 Correct 219 ms 84328 KB Output is correct
30 Correct 309 ms 96496 KB Output is correct
31 Correct 506 ms 128340 KB Output is correct
32 Correct 449 ms 127080 KB Output is correct
33 Correct 496 ms 127208 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 75512 KB Output is correct
2 Correct 75 ms 75768 KB Output is correct
3 Correct 71 ms 75512 KB Output is correct
4 Correct 74 ms 75640 KB Output is correct
5 Correct 77 ms 75692 KB Output is correct
6 Correct 66 ms 75412 KB Output is correct
7 Correct 65 ms 75384 KB Output is correct
8 Correct 67 ms 75512 KB Output is correct
9 Correct 67 ms 75512 KB Output is correct
10 Correct 71 ms 75512 KB Output is correct
11 Correct 73 ms 75644 KB Output is correct
12 Correct 71 ms 75640 KB Output is correct
13 Correct 72 ms 75768 KB Output is correct
14 Correct 77 ms 75896 KB Output is correct
15 Correct 76 ms 75484 KB Output is correct
16 Correct 72 ms 75640 KB Output is correct
17 Correct 68 ms 75428 KB Output is correct
18 Correct 1520 ms 95868 KB Output is correct
19 Correct 245 ms 79588 KB Output is correct
20 Correct 243 ms 79204 KB Output is correct
21 Correct 270 ms 79164 KB Output is correct
22 Correct 283 ms 79352 KB Output is correct
23 Correct 253 ms 79608 KB Output is correct
24 Correct 296 ms 79224 KB Output is correct
25 Correct 293 ms 79472 KB Output is correct
26 Correct 312 ms 79588 KB Output is correct
27 Correct 824 ms 93008 KB Output is correct
28 Correct 678 ms 85964 KB Output is correct
29 Correct 739 ms 91416 KB Output is correct
30 Correct 1378 ms 111396 KB Output is correct
31 Correct 80 ms 75640 KB Output is correct
32 Correct 1088 ms 93680 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 75512 KB Output is correct
2 Correct 75 ms 75768 KB Output is correct
3 Correct 71 ms 75512 KB Output is correct
4 Correct 74 ms 75640 KB Output is correct
5 Correct 77 ms 75692 KB Output is correct
6 Correct 66 ms 75412 KB Output is correct
7 Correct 65 ms 75384 KB Output is correct
8 Correct 67 ms 75512 KB Output is correct
9 Correct 67 ms 75512 KB Output is correct
10 Correct 71 ms 75512 KB Output is correct
11 Correct 73 ms 75644 KB Output is correct
12 Correct 71 ms 75640 KB Output is correct
13 Correct 72 ms 75768 KB Output is correct
14 Correct 77 ms 75896 KB Output is correct
15 Correct 76 ms 75484 KB Output is correct
16 Correct 72 ms 75640 KB Output is correct
17 Correct 68 ms 75428 KB Output is correct
18 Correct 1520 ms 95868 KB Output is correct
19 Correct 245 ms 79588 KB Output is correct
20 Correct 243 ms 79204 KB Output is correct
21 Correct 270 ms 79164 KB Output is correct
22 Correct 283 ms 79352 KB Output is correct
23 Correct 253 ms 79608 KB Output is correct
24 Correct 296 ms 79224 KB Output is correct
25 Correct 293 ms 79472 KB Output is correct
26 Correct 312 ms 79588 KB Output is correct
27 Correct 824 ms 93008 KB Output is correct
28 Correct 678 ms 85964 KB Output is correct
29 Correct 739 ms 91416 KB Output is correct
30 Correct 1378 ms 111396 KB Output is correct
31 Correct 80 ms 75640 KB Output is correct
32 Correct 1088 ms 93680 KB Output is correct
33 Correct 436 ms 122732 KB Output is correct
34 Correct 590 ms 147180 KB Output is correct
35 Correct 529 ms 141044 KB Output is correct
36 Correct 438 ms 123536 KB Output is correct
37 Correct 187 ms 86508 KB Output is correct
38 Correct 261 ms 95980 KB Output is correct
39 Correct 336 ms 87016 KB Output is correct
40 Correct 336 ms 86892 KB Output is correct
41 Correct 186 ms 85600 KB Output is correct
42 Correct 365 ms 99948 KB Output is correct
43 Correct 445 ms 122856 KB Output is correct
44 Correct 659 ms 147020 KB Output is correct
45 Correct 494 ms 141232 KB Output is correct
46 Correct 407 ms 123628 KB Output is correct
47 Correct 195 ms 84328 KB Output is correct
48 Correct 254 ms 96336 KB Output is correct
49 Correct 535 ms 128360 KB Output is correct
50 Correct 502 ms 127080 KB Output is correct
51 Correct 471 ms 127084 KB Output is correct
52 Correct 339 ms 86972 KB Output is correct
53 Correct 335 ms 86892 KB Output is correct
54 Correct 158 ms 85488 KB Output is correct
55 Correct 340 ms 99936 KB Output is correct
56 Correct 481 ms 122732 KB Output is correct
57 Correct 545 ms 147048 KB Output is correct
58 Correct 550 ms 141224 KB Output is correct
59 Correct 466 ms 123704 KB Output is correct
60 Correct 219 ms 84328 KB Output is correct
61 Correct 309 ms 96496 KB Output is correct
62 Correct 506 ms 128340 KB Output is correct
63 Correct 449 ms 127080 KB Output is correct
64 Correct 496 ms 127208 KB Output is correct
65 Correct 651 ms 89764 KB Output is correct
66 Correct 607 ms 89864 KB Output is correct
67 Correct 548 ms 88824 KB Output is correct
68 Correct 786 ms 102692 KB Output is correct
69 Correct 1018 ms 125696 KB Output is correct
70 Correct 1713 ms 149976 KB Output is correct
71 Correct 1169 ms 143976 KB Output is correct
72 Correct 1182 ms 126708 KB Output is correct
73 Correct 643 ms 87244 KB Output is correct
74 Correct 798 ms 99276 KB Output is correct
75 Correct 926 ms 130456 KB Output is correct
76 Correct 1290 ms 130008 KB Output is correct
77 Correct 1189 ms 130056 KB Output is correct
78 Correct 338 ms 82828 KB Output is correct
79 Correct 559 ms 88280 KB Output is correct
80 Correct 415 ms 88044 KB Output is correct
81 Correct 364 ms 84840 KB Output is correct
82 Correct 471 ms 85004 KB Output is correct
83 Correct 165 ms 76784 KB Output is correct
84 Correct 376 ms 88196 KB Output is correct
85 Correct 385 ms 88012 KB Output is correct
86 Correct 371 ms 84952 KB Output is correct
87 Correct 408 ms 86844 KB Output is correct
88 Correct 384 ms 88112 KB Output is correct
89 Correct 419 ms 88040 KB Output is correct
90 Correct 321 ms 85028 KB Output is correct
91 Correct 355 ms 84504 KB Output is correct