oj.uz

Submission #598718

# Submission time Handle Problem Language Result Execution time Memory
598718 2022-07-18T19:28:53 Z GusterGoose27 Land of the Rainbow Gold (APIO17_rainbow) C++11
100 / 100
 1266 ms 487880 KB 
#include <bits/stdc++.h>

using namespace std;

typedef vector<pair<int, vector<int>>> plist;
typedef pair<int, int> pii;

const int MAXN = 2e5+5;
set<int> serpx[MAXN]; // points
set<int> serpy_c[MAXN]; // corners
set<int> serp_c[MAXN]; // corners, (i, j) refers to bottom left of square i, j
vector<pii> rangesx[MAXN];
vector<pii> rangesy[MAXN];

bool valid(int x, int y, set<int> s[] = serp_c) {
	if (x < 0) return 0;
	return (s[x].find(y) != s[x].end());
}

bool adjy(int x, int y) {
	return valid(x, y, serpx) || valid(x-1, y, serpx);
}

bool adjx(int x, int y) {
	return valid(x, y, serpx) || valid(x, y-1, serpx);
}

bool xempty(int y, int x1, int x2) {
	return (serpy_c[y].lower_bound(x1) == serpy_c[y].upper_bound(x2));
}

bool yempty(int x, int y1, int y2) {
	return (serp_c[x].lower_bound(y1) == serp_c[x].upper_bound(y2));
}

int getxcc(int y, int x1, int x2) {
	int mn = -1;
	int mx = rangesy[y].size();
	while (mx > mn+1) {
		int cur = (mn+mx)/2;
		if (rangesy[y][cur].second < x1) mn = cur;
		else mx = cur;
	}
	int l = mn;
	mn = -1;
	mx = rangesy[y].size();
	while (mx > mn+1) {
		int cur = (mn+mx)/2;
		if (rangesy[y][cur].first > x2) mx = cur;
		else mn = cur;
	}
	return mx-l-1;
}

int getycc(int x, int y1, int y2) {
	int mn = -1;
	int mx = rangesx[x].size();
	while (mx > mn+1) {
		int cur = (mn+mx)/2;
		if (rangesx[x][cur].second < y1) mn = cur;
		else mx = cur;
	}
	int l = mn;
	mn = -1;
	mx = rangesx[x].size();
	while (mx > mn+1) {
		int cur = (mn+mx)/2;
		if (rangesx[x][cur].first > y2) mx = cur;
		else mn = cur;
	}
	return mx-l-1;
}

class intree {
public:
	int ymin, ymax;
	int xmin, xmax;
	int point_count = 0;
	int edge_net = 0;
	int u_cut = 0;
	int r_cut = 0;
	int sq_count = 0;
	intree *l = nullptr;
	intree *r = nullptr;
	intree(plist &vals, int y1, int y2, int lp, int rp) {
		ymin = y1;
		ymax = y2;
		xmin = vals[lp].first;
		xmax = vals[rp].first;
		if (lp == rp) make_spec(vals[lp].second);
		else {
			int m = (lp+rp)/2;
			l = new intree(vals, y1, y2, lp, m);
			r = new intree(vals, y1, y2, m+1, rp);
			merge(vals, m);
		}
	}
	void make_spec(vector<int> &vals) {
		point_count = vals.size();
		for (int v: vals) {
			if (adjx(xmin, v)) r_cut++;
			if (v < ymax) {
				if (adjy(xmin, v)) edge_net++;
				//if (valid(xmin, v, serpx)) r_cut--;
			}
		}
		if (vals.back() == ymax) {
			if (adjy(xmin, ymax)) u_cut++;
		}
		for (auto it = serpx[xmin].lower_bound(ymin); it != serpx[xmin].end() && (*it) <= ymax; it++) sq_count++;
	}
	void merge(plist &vals, int m) {
		point_count = l->point_count+r->point_count;
		edge_net = l->edge_net+r->edge_net+l->r_cut;
		u_cut = l->u_cut+r->u_cut;
		r_cut = r->r_cut;
		sq_count = l->sq_count+r->sq_count;
		// if (vals[m].first == vals[m+1].first && vals[m].second.back() == ymax && vals[m+1].second.back() == ymax) {
		// 	u_cut--;
		// }
	}
	int query(int x1, int x2, int uc, int dc) {
		if (xmin > x2 || xmax < x1) return 0;
		if (xmin >= x1 && xmax <= x2) {
			int lc = (xmin > x1);
			int rc = (xmax < x2);
			int ans = edge_net-point_count;
			if (rc) ans += r_cut;
			if (uc) ans += u_cut;
			return ans;
		}
		int lq = l->query(x1, x2, uc, dc);
		int rq = r->query(x1, x2, uc, dc);
		// if (lq == -1) return rq;
		// if (rq == -1) return lq;
		return lq+rq;
	}
	int query2(int x1, int x2) {
		if (xmin > x2 || xmax < x1) return 0;
		if (xmin >= x1 && xmax <= x2) {
			return sq_count;
		}
		return l->query2(x1, x2)+r->query2(x1, x2);
	}
};

class stree {
public:
	int ymin, ymax;
	plist vals;
	intree *curtree = nullptr;
	stree *l = nullptr;
	stree *r = nullptr;
	stree(int y1, int y2) {
		ymin = y1;
		ymax = y2;
		if (ymin == ymax) make_vals_spec();
		else {
			int m = (ymin+ymax)/2;
			l = new stree(y1, m);
			r = new stree(m+1, y2);
			merge_vals();
		}
		if (vals.empty()) return;
		curtree = new intree(vals, y1, y2, 0, vals.size()-1);
	}
	void make_vals_spec() {
		for (int x: serpy_c[ymin]) vals.push_back(pair<int, vector<int>>(x, {ymin}));
	}
	vector<int> merge_vec(vector<int> &a, vector<int> &b) {
		int g = 0;
		int h = 0;
		vector<int> v;
		while (g < a.size() || h < b.size()) {
			if (g == a.size()) {
				v.push_back(b[h++]);
				continue;
			}
			if (h == b.size()) {
				v.push_back(a[g++]);
				continue;
			}
			if (a[g] < b[h]) {
				v.push_back(a[g++]);
			}
			else v.push_back(b[h++]);
		}
		return v;
	}
	void merge_vals() {
		int a = 0;
		int b = 0;
		while (a < l->vals.size() || b < r->vals.size()) {
			if (a == l->vals.size()) {
				vals.push_back(r->vals[b++]);
				continue;
			}
			if (b == r->vals.size()) {
				vals.push_back(l->vals[a++]);
				continue;
			}
			if (l->vals[a].first == r->vals[b].first) {
				vals.push_back(pair<int, vector<int>>(l->vals[a].first, merge_vec(l->vals[a].second, r->vals[b].second)));
				a++; b++;
				continue;
			}
			if (l->vals[a].first < r->vals[b].first) {
				vals.push_back(l->vals[a++]);
			}
			else vals.push_back(r->vals[b++]);
		}
	}
	int query(int x1, int x2, int y1, int y2) {
		if (ymin > y2 || ymax < y1 || curtree == nullptr) return 0;
		if (ymin >= y1 && ymax <= y2) {
			return curtree->query(x1, x2, ymax < y2, ymin > y1);
		}
		int lq = l->query(x1, x2, y1, y2);
		int rq = r->query(x1, x2, y1, y2);
		// if (lq == -1) return rq;
		// if (rq == -1) return lq;
		return lq+rq;
	}
	int query2(int x1, int x2, int y1, int y2) {
		if (ymin > y2 || ymax < y1 || curtree == nullptr) return 0;
		if (ymin >= y1 && ymax <= y2) return curtree->query2(x1, x2);
		return l->query2(x1, x2, y1, y2)+r->query2(x1, x2, y1, y2);
	}
};

stree *tree;

void color(int r, int c) {
	serpx[r].insert(c);
	serpy_c[c].insert(r);
	serpy_c[c].insert(r+1);
	serpy_c[c+1].insert(r);
	serpy_c[c+1].insert(r+1);
	serp_c[r].insert(c);
	serp_c[r].insert(c+1);
	serp_c[r+1].insert(c);
	serp_c[r+1].insert(c+1);
}

void init(int t1, int t2, int sr, int sc, int m, char *s) {
	sr--; sc--;
	color(sr, sc);
	for (int i = 0; i < m; i++) {
		if (s[i] == 'N') sr--;
		if (s[i] == 'S') sr++;
		if (s[i] == 'W') sc--;
		if (s[i] == 'E') sc++;
		color(sr, sc);
	}
	tree = new stree(0, MAXN-1);
	pii prev;
	for (int x = 0; x < MAXN; x++) {
		prev = pii(-1, -1);
		for (int y: serp_c[x]) {
			if (prev.second == -1) prev = pii(y, y);
			else prev.second++;
			if (!adjy(x, y)) {
				rangesx[x].push_back(prev);
				prev = pii(-1, -1);
			}
		}
	}
	for (int y = 0; y < MAXN; y++) {
		prev = pii(-1, -1);
		for (int x: serpy_c[y]) {
			if (prev.second == -1) prev = pii(x, x);
			else prev.second++;
			if (!adjx(x, y)) {
				rangesy[y].push_back(prev);
				prev = pii(-1, -1);
			}
		}
	}
}

int colour(int x1, int y1, int x2, int y2) {
	x1--;
	y1--;
	int sqs = tree->query2(x1, x2-1, y1, y2-1);
	if (sqs == 0) return 1;
	int ans = tree->query(x1, x2, y1, y2)-sqs;
	if (xempty(y1, x1, x2) && xempty(y2, x1, x2) && yempty(x1, y1, y2) && yempty(x2, y1, y2)) return ans+2;
	int cc = getxcc(y1, x1, x2)+getxcc(y2, x1, x2)+getycc(x1, y1, y2)+getycc(x2, y1, y2);
	cc -= valid(x1, y1);
	cc -= valid(x1, y2);
	cc -= valid(x2, y1);
	cc -= valid(x2, y2);
	return ans+cc+1;
}

// int main() {
// 	init(6, 4, 3, 3, 4, "WSEN");
// 	cout << colour(2, 1, 5, 4) << "\n";
// 	return 0;
// }

Compilation message

rainbow.cpp: In member function 'int intree::query(int, int, int, int)':
rainbow.cpp:125:8: warning: unused variable 'lc' [-Wunused-variable]
  125 |    int lc = (xmin > x1);
      |        ^~
rainbow.cpp: In member function 'std::vector<int> stree::merge_vec(std::vector<int>&, std::vector<int>&)':
rainbow.cpp:174:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |   while (g < a.size() || h < b.size()) {
      |          ~~^~~~~~~~~~
rainbow.cpp:174:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |   while (g < a.size() || h < b.size()) {
      |                          ~~^~~~~~~~~~
rainbow.cpp:175:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |    if (g == a.size()) {
      |        ~~^~~~~~~~~~~
rainbow.cpp:179:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |    if (h == b.size()) {
      |        ~~^~~~~~~~~~~
rainbow.cpp: In member function 'void stree::merge_vals()':
rainbow.cpp:193:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |   while (a < l->vals.size() || b < r->vals.size()) {
      |          ~~^~~~~~~~~~~~~~~~
rainbow.cpp:193:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |   while (a < l->vals.size() || b < r->vals.size()) {
      |                                ~~^~~~~~~~~~~~~~~~
rainbow.cpp:194:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |    if (a == l->vals.size()) {
      |        ~~^~~~~~~~~~~~~~~~~
rainbow.cpp:198:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |    if (b == r->vals.size()) {
      |        ~~^~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 63052 KB Output is correct
2 Correct 45 ms 63972 KB Output is correct
3 Correct 40 ms 63352 KB Output is correct
4 Correct 42 ms 63392 KB Output is correct
5 Correct 45 ms 64156 KB Output is correct
6 Correct 40 ms 62924 KB Output is correct
7 Correct 43 ms 62892 KB Output is correct
8 Correct 39 ms 62876 KB Output is correct
9 Correct 39 ms 62912 KB Output is correct
10 Correct 39 ms 62932 KB Output is correct
11 Correct 41 ms 63308 KB Output is correct
12 Correct 43 ms 63668 KB Output is correct
13 Correct 49 ms 64576 KB Output is correct
14 Correct 47 ms 64504 KB Output is correct
15 Correct 41 ms 62884 KB Output is correct
16 Correct 39 ms 62816 KB Output is correct
17 Correct 39 ms 62840 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 62816 KB Output is correct
2 Correct 39 ms 62840 KB Output is correct
3 Correct 561 ms 127188 KB Output is correct
4 Correct 935 ms 172900 KB Output is correct
5 Correct 985 ms 175788 KB Output is correct
6 Correct 698 ms 147012 KB Output is correct
7 Correct 867 ms 148608 KB Output is correct
8 Correct 108 ms 63656 KB Output is correct
9 Correct 955 ms 172908 KB Output is correct
10 Correct 1010 ms 175700 KB Output is correct
11 Correct 752 ms 146840 KB Output is correct
12 Correct 635 ms 162728 KB Output is correct
13 Correct 669 ms 172752 KB Output is correct
14 Correct 695 ms 175684 KB Output is correct
15 Correct 589 ms 146908 KB Output is correct
16 Correct 672 ms 138944 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 62884 KB Output is correct
2 Correct 722 ms 169536 KB Output is correct
3 Correct 568 ms 484376 KB Output is correct
4 Correct 379 ms 323876 KB Output is correct
5 Correct 436 ms 300244 KB Output is correct
6 Correct 148 ms 83732 KB Output is correct
7 Correct 263 ms 102092 KB Output is correct
8 Correct 573 ms 165288 KB Output is correct
9 Correct 572 ms 161568 KB Output is correct
10 Correct 185 ms 85720 KB Output is correct
11 Correct 381 ms 154460 KB Output is correct
12 Correct 686 ms 169684 KB Output is correct
13 Correct 540 ms 484380 KB Output is correct
14 Correct 379 ms 323900 KB Output is correct
15 Correct 430 ms 300320 KB Output is correct
16 Correct 135 ms 79308 KB Output is correct
17 Correct 244 ms 102444 KB Output is correct
18 Correct 590 ms 179076 KB Output is correct
19 Correct 603 ms 317708 KB Output is correct
20 Correct 585 ms 317760 KB Output is correct
21 Correct 582 ms 165268 KB Output is correct
22 Correct 570 ms 161500 KB Output is correct
23 Correct 178 ms 85628 KB Output is correct
24 Correct 347 ms 154492 KB Output is correct
25 Correct 720 ms 169648 KB Output is correct
26 Correct 574 ms 484436 KB Output is correct
27 Correct 362 ms 324060 KB Output is correct
28 Correct 424 ms 300368 KB Output is correct
29 Correct 145 ms 79368 KB Output is correct
30 Correct 239 ms 102400 KB Output is correct
31 Correct 591 ms 179120 KB Output is correct
32 Correct 596 ms 317840 KB Output is correct
33 Correct 570 ms 317488 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 63052 KB Output is correct
2 Correct 45 ms 63972 KB Output is correct
3 Correct 40 ms 63352 KB Output is correct
4 Correct 42 ms 63392 KB Output is correct
5 Correct 45 ms 64156 KB Output is correct
6 Correct 40 ms 62924 KB Output is correct
7 Correct 43 ms 62892 KB Output is correct
8 Correct 39 ms 62876 KB Output is correct
9 Correct 39 ms 62912 KB Output is correct
10 Correct 39 ms 62932 KB Output is correct
11 Correct 41 ms 63308 KB Output is correct
12 Correct 43 ms 63668 KB Output is correct
13 Correct 49 ms 64576 KB Output is correct
14 Correct 47 ms 64504 KB Output is correct
15 Correct 41 ms 62884 KB Output is correct
16 Correct 39 ms 62816 KB Output is correct
17 Correct 39 ms 62840 KB Output is correct
18 Correct 1035 ms 158520 KB Output is correct
19 Correct 162 ms 69208 KB Output is correct
20 Correct 132 ms 67184 KB Output is correct
21 Correct 132 ms 68044 KB Output is correct
22 Correct 164 ms 68996 KB Output is correct
23 Correct 151 ms 69196 KB Output is correct
24 Correct 169 ms 67360 KB Output is correct
25 Correct 165 ms 68436 KB Output is correct
26 Correct 147 ms 69372 KB Output is correct
27 Correct 445 ms 114076 KB Output is correct
28 Correct 309 ms 88524 KB Output is correct
29 Correct 484 ms 105188 KB Output is correct
30 Correct 1036 ms 182664 KB Output is correct
31 Correct 40 ms 62996 KB Output is correct
32 Correct 773 ms 107588 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 63052 KB Output is correct
2 Correct 45 ms 63972 KB Output is correct
3 Correct 40 ms 63352 KB Output is correct
4 Correct 42 ms 63392 KB Output is correct
5 Correct 45 ms 64156 KB Output is correct
6 Correct 40 ms 62924 KB Output is correct
7 Correct 43 ms 62892 KB Output is correct
8 Correct 39 ms 62876 KB Output is correct
9 Correct 39 ms 62912 KB Output is correct
10 Correct 39 ms 62932 KB Output is correct
11 Correct 41 ms 63308 KB Output is correct
12 Correct 43 ms 63668 KB Output is correct
13 Correct 49 ms 64576 KB Output is correct
14 Correct 47 ms 64504 KB Output is correct
15 Correct 41 ms 62884 KB Output is correct
16 Correct 39 ms 62816 KB Output is correct
17 Correct 39 ms 62840 KB Output is correct
18 Correct 1035 ms 158520 KB Output is correct
19 Correct 162 ms 69208 KB Output is correct
20 Correct 132 ms 67184 KB Output is correct
21 Correct 132 ms 68044 KB Output is correct
22 Correct 164 ms 68996 KB Output is correct
23 Correct 151 ms 69196 KB Output is correct
24 Correct 169 ms 67360 KB Output is correct
25 Correct 165 ms 68436 KB Output is correct
26 Correct 147 ms 69372 KB Output is correct
27 Correct 445 ms 114076 KB Output is correct
28 Correct 309 ms 88524 KB Output is correct
29 Correct 484 ms 105188 KB Output is correct
30 Correct 1036 ms 182664 KB Output is correct
31 Correct 40 ms 62996 KB Output is correct
32 Correct 773 ms 107588 KB Output is correct
33 Correct 722 ms 169536 KB Output is correct
34 Correct 568 ms 484376 KB Output is correct
35 Correct 379 ms 323876 KB Output is correct
36 Correct 436 ms 300244 KB Output is correct
37 Correct 148 ms 83732 KB Output is correct
38 Correct 263 ms 102092 KB Output is correct
39 Correct 573 ms 165288 KB Output is correct
40 Correct 572 ms 161568 KB Output is correct
41 Correct 185 ms 85720 KB Output is correct
42 Correct 381 ms 154460 KB Output is correct
43 Correct 686 ms 169684 KB Output is correct
44 Correct 540 ms 484380 KB Output is correct
45 Correct 379 ms 323900 KB Output is correct
46 Correct 430 ms 300320 KB Output is correct
47 Correct 135 ms 79308 KB Output is correct
48 Correct 244 ms 102444 KB Output is correct
49 Correct 590 ms 179076 KB Output is correct
50 Correct 603 ms 317708 KB Output is correct
51 Correct 585 ms 317760 KB Output is correct
52 Correct 582 ms 165268 KB Output is correct
53 Correct 570 ms 161500 KB Output is correct
54 Correct 178 ms 85628 KB Output is correct
55 Correct 347 ms 154492 KB Output is correct
56 Correct 720 ms 169648 KB Output is correct
57 Correct 574 ms 484436 KB Output is correct
58 Correct 362 ms 324060 KB Output is correct
59 Correct 424 ms 300368 KB Output is correct
60 Correct 145 ms 79368 KB Output is correct
61 Correct 239 ms 102400 KB Output is correct
62 Correct 591 ms 179120 KB Output is correct
63 Correct 596 ms 317840 KB Output is correct
64 Correct 570 ms 317488 KB Output is correct
65 Correct 561 ms 127188 KB Output is correct
66 Correct 935 ms 172900 KB Output is correct
67 Correct 985 ms 175788 KB Output is correct
68 Correct 698 ms 147012 KB Output is correct
69 Correct 867 ms 148608 KB Output is correct
70 Correct 108 ms 63656 KB Output is correct
71 Correct 955 ms 172908 KB Output is correct
72 Correct 1010 ms 175700 KB Output is correct
73 Correct 752 ms 146840 KB Output is correct
74 Correct 635 ms 162728 KB Output is correct
75 Correct 669 ms 172752 KB Output is correct
76 Correct 695 ms 175684 KB Output is correct
77 Correct 589 ms 146908 KB Output is correct
78 Correct 672 ms 138944 KB Output is correct
79 Correct 1229 ms 168892 KB Output is correct
80 Correct 1266 ms 165000 KB Output is correct
81 Correct 539 ms 89128 KB Output is correct
82 Correct 655 ms 157772 KB Output is correct
83 Correct 826 ms 173088 KB Output is correct
84 Correct 639 ms 487880 KB Output is correct
85 Correct 438 ms 327564 KB Output is correct
86 Correct 504 ms 303836 KB Output is correct
87 Correct 192 ms 82940 KB Output is correct
88 Correct 289 ms 106060 KB Output is correct
89 Correct 647 ms 182596 KB Output is correct
90 Correct 716 ms 321152 KB Output is correct
91 Correct 825 ms 321052 KB Output is correct