Submission #598062

#	Time	Username	Problem	Language	Result	Execution time	Memory
598062		GusterGoose27	Land of the Rainbow Gold (APIO17_rainbow)	C++11	0 / 100	407 ms	529548 KiB

rainbow

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2e5+1;
int n, m;
set<int> serp[MAXN];
set<int> serpy[MAXN];

bool valid(int x, int y) {
	return (serp[x].find(y) != serp[x].end());
}

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

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

vector<int> vec_merge(vector<int> &a, vector<int> &b) {
	vector<int> v;
	int l = 0;
	int r = 0;
	while (l < a.size() || r < b.size()) {
		if (l == a.size()) {
			v.push_back(b[r]);
			r++;
			continue;
		}
		if (r == b.size()) {
			v.push_back(a[l]);
			l++;
			continue;
		}
		if (a[l] < b[r]) {
			v.push_back(a[l]);
			l++;
			continue;
		}
		v.push_back(b[r]);
		r++;
	}
	return v;
}

bool right_seam(int x, int y) {
	return valid(x, y) && valid(x, y+1) && valid(x+1, y) && valid(x+1, y+1);
}

bool dubx(int x, int y) {
	return valid(x, y) && valid(x+1, y);
}

bool duby(int x, int y) {
	return valid(x, y) && valid(x, y+1);
}

class intree {
public:
	int lval, rval;
	int ymin, ymax;
	int n;
	intree *l = nullptr;
	intree *r = nullptr;
	int vert_count = 0;
	int u_cut = 0;
	int r_cut = 0;
	int u_sq = 0;
	int r_sq = 0;
	int num_edges = 0;
	int num_sqs = 0;
	int ladj = 0; // edges minus adj nodes
	int radj = 0;
	int uadj = 0;
	int dadj = 0;
	intree(vector<pair<int, vector<int>>> &vals, int lpos, int rpos, int y1, int y2) {
		ymin = y1;
		ymax = y2;
		lval = vals[lpos].first;
		rval = vals[rpos].first;
		n = rpos-lpos+1;
		if (lpos == rpos) special_create(vals[lpos]);
		else {
			int m = (lpos+rpos)/2;
			l = new intree(vals, lpos, m, y1, y2);
			r = new intree(vals, m+1, rpos, y1, y2);
			merge(vals, m);
		}
	}
	void special_create(pair<int, vector<int>> &v) {
		int x = v.first;
		for (int y: v.second) {
			if (valid(x+1, y)) r_cut++;
		}
		if (v.second.back() == ymax) {
			if (valid(x, ymax+1)) u_cut++;
			uadj++;
		}
		if (v.second[0] == ymin) dadj++;
		ladj = radj = v.second.size();
		for (int i = 0; i < v.second.size()-1; i++) {
			if (v.second[i] == v.second[i+1]-1) {
				ladj--;
				radj--;
				num_edges++;
				if (duby(x+1, v.second[i])) r_sq++;
			}
		}
		vert_count = v.second.size();
	}
	void merge(vector<pair<int, vector<int>>> &vals, int m) {
		vert_count = l->vert_count+r->vert_count; //
		num_edges = l->num_edges+r->num_edges+l->r_cut; //
		num_sqs = l->num_sqs+r->num_sqs+l->r_sq; //
		ladj = l->ladj; //
		radj = r->radj; //
		uadj = l->uadj+r->uadj; //
		dadj = l->dadj+r->dadj; //
		u_cut = l->u_cut+r->u_cut; //
		r_cut = r->r_cut; //
		r_sq = r->r_sq; //
		u_sq = l->u_sq+r->u_sq; //
		int xdiv = vals[m].first;
		if (vals[m].first+1 == vals[m+1].first) {
			if (vals[m].second.back() == ymax && vals[m+1].second.back() == ymax) {
				uadj--;
				if (dubx(xdiv, ymax+1)) u_sq++;
			}
			if (vals[m].second[0] == ymin && vals[m+1].second[0] == ymin) dadj--;
		}
	}
	int query(int x1, int x2, int uc, int dc) { // srmask bits go right up left down. Return e-v-sq
		if (lval > x2 || rval < x1 || vert_count == 0) return -1;
		if (lval >= x1 && rval <= x2) {
			int srmask = 2*uc+8*dc;
			if (rval < x2) srmask++;
			if (lval > x1) srmask += 4;
			int s = num_edges-vert_count-num_sqs;
			if (srmask & 1) {
				s += r_cut-r_sq;
			}
			if (srmask & 2) {
				s += u_cut-u_sq;
			}
			if ((srmask & 1) == 0) {
				s += radj;
			}
			if ((srmask & 2) == 0) {
				s += uadj;
			}
			if ((srmask & 4) == 0) {
				s += ladj;
			}
			if ((srmask & 8) == 0) {
				s += dadj;
			}
			if (srmask & 3) s -= right_seam(rval, ymax);
			if ((srmask & 2) && !(srmask & 1)) s -= duby(rval, ymax);
			if (!(srmask & 2) && (srmask & 1)) s -= dubx(rval, ymax);
			if ((srmask & 2) && !(srmask & 4)) s -= duby(lval, ymax);
			if ((srmask & 1) && !(srmask & 8)) s -= dubx(rval, ymin);
			return s;
		}
		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;
	}
};

class stree {
public:
	intree *cur_tree;
	int y1, y2;
	stree *l = nullptr;
	stree *r = nullptr;
	vector<pair<int, vector<int>>> vals;
	stree(int dval, int uval) {
		y1 = dval;
		y2 = uval;
		if (y1 == y2) make_vals();
		else {
			int m = (y1+y2)/2;
			l = new stree(dval, m);
			r = new stree(m+1, uval);
			merge_vals();
		}
		if (vals.size() > 0) cur_tree = new intree(vals, 0, vals.size()-1, y1, y2);
	}
	void make_vals() {
		for (int x: serpy[y1]) {
			vals.push_back(pair<int, vector<int>>(x, {y1}));
		}
	}
	void merge_vals() {
		int m1 = l->vals.size();
		int m2 = r->vals.size();
		int a = 0;
		int b = 0;
		while (a < m1 || b < m2) {
			if (a == m1) {
				vals.push_back(r->vals[b]);
				b++;
				continue;
			}
			if (b == m2) {
				vals.push_back(l->vals[a]);
				a++;
				continue;
			}
			if (l->vals[a].first == r->vals[b].first) {
				vals.push_back(pair<int, vector<int>>(l->vals[a].first, vec_merge(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]);
				a++;
				continue;
			}
			vals.push_back(r->vals[b]);
			b++;
		}
	}
	int query(int dy, int uy, int x1, int x2) {
		if (cur_tree == nullptr) return -1;
		if (y1 > uy || y2 < dy) return -1;
		if (y1 >= dy && y2 <= uy) {
			int uadj = 0;
			int dadj = 0;
			if (y1 > dy) dadj = 1;
			if (y2 < uy) uadj = 1;
			return cur_tree->query(x1, x2, uadj, dadj);
		}
		int lq = l->query(dy, uy, x1, x2);
		int rq = r->query(dy, uy, x1, x2);
		if (lq == -1) return rq;
		if (rq == -1) return lq;
		return lq+rq;
	}
};

stree *tree;

void color(int r, int c) {
	serp[r].insert(c);
}

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] == 'W') sc--;
		if (s[i] == 'S') sr++;
		if (s[i] == 'E') sc++;
		color(sr, sc);
	}
	for (int x = 0; x < MAXN; x++) {
		for (int y: serp[x]) {
			serpy[y].insert(x);
		}
	}
	tree = new stree(0, MAXN-1);
}

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

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

Compilation message (stderr)

rainbow.cpp: In function 'std::vector<int> vec_merge(std::vector<int>&, std::vector<int>&)':
rainbow.cpp:28:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  while (l < a.size() || r < b.size()) {
      |         ~~^~~~~~~~~~
rainbow.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  while (l < a.size() || r < b.size()) {
      |                         ~~^~~~~~~~~~
rainbow.cpp:29:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   if (l == a.size()) {
      |       ~~^~~~~~~~~~~
rainbow.cpp:34:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   if (r == b.size()) {
      |       ~~^~~~~~~~~~~
rainbow.cpp: In member function 'void intree::special_create(std::pair<int, std::vector<int> >&)':
rainbow.cpp:105:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for (int i = 0; i < v.second.size()-1; i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26