Submission #559697

#TimeUsernameProblemLanguageResultExecution timeMemory
559697SSRSLand of the Rainbow Gold (APIO17_rainbow)C++14
0 / 100
9 ms1108 KiB
#include <bits/stdc++.h> #include "rainbow.h" using namespace std; int xmin, xmax, ymin, ymax; struct range_tree{ int N; vector<vector<int>> ST; range_tree(){ } range_tree(int N2){ N = 1; while (N < N2){ N *= 2; } ST = vector<vector<int>>(N * 2 - 1); } void add(int X, int Y){ X += N - 1; ST[X].push_back(Y); while (X > 0){ X = (X - 1) / 2; ST[X].push_back(Y); } } void build(){ for (int i = 0; i < N * 2 - 1; i++){ sort(ST[i].begin(), ST[i].end()); } } int rectangle_sum(int L, int R, int U, int D, int i, int l, int r){ if (r <= L || R <= l){ return 0; } else if (L <= l && r <= R){ return lower_bound(ST[i].begin(), ST[i].end(), D) - lower_bound(ST[i].begin(), ST[i].end(), U); } else { int m = (l + r) / 2; return rectangle_sum(L, R, U, D, i * 2 + 1, l, m) + rectangle_sum(L, R, U, D, i * 2 + 2, m, r); } } int rectangle_sum(int L, int R, int U, int D){ return rectangle_sum(L, R, U, D, 0, 0, N); } }; range_tree ST1, ST2, ST3, ST4; void init(int R, int C, int sr, int sc, int M, char *S){ assert(R <= 1000 && C <= 1000); sr--; sc--; vector<int> x(M + 1), y(M + 1); x[0] = sr; y[0] = sc; for (int i = 0; i < M; i++){ x[i + 1] = x[i]; y[i + 1] = y[i]; if (S[i] == 'N'){ x[i + 1]--; } if (S[i] == 'S'){ x[i + 1]++; } if (S[i] == 'E'){ y[i + 1]++; } if (S[i] == 'W'){ y[i + 1]--; } } xmin = sr; xmax = sr; ymin = sc; ymax = sc; for (int i = 1; i <= M; i++){ xmin = min(xmin, x[i]); xmax = max(xmax, x[i]); ymin = min(ymin, y[i]); ymax = max(ymax, y[i]); } set<pair<int, int>> st1, st2, st3, st4; for (int i = 0; i <= M; i++){ st1.insert(make_pair(x[i], y[i])); st2.insert(make_pair(x[i], y[i])); st2.insert(make_pair(x[i] - 1, y[i])); st3.insert(make_pair(x[i], y[i])); st3.insert(make_pair(x[i], y[i] - 1)); st4.insert(make_pair(x[i], y[i])); st4.insert(make_pair(x[i] - 1, y[i])); st4.insert(make_pair(x[i], y[i] - 1)); st4.insert(make_pair(x[i] - 1, y[i] - 1)); } ST1 = range_tree(R + 1); for (auto P : st1){ ST1.add(P.first, P.second); } ST1.build(); ST2 = range_tree(R); for (auto P : st2){ ST2.add(P.first, P.second); } ST2.build(); ST3 = range_tree(R + 1); for (auto P : st3){ ST3.add(P.first, P.second); } ST3.build(); ST4 = range_tree(R); for (auto P : st4){ ST4.add(P.first, P.second); } ST4.build(); } int colour(int ar, int ac, int br, int bc){ ar--; ac--; int ans = 1; ans -= ST1.rectangle_sum(ar, br, ac, bc); ans += ST2.rectangle_sum(ar, br - 1, ac, bc); ans += ST3.rectangle_sum(ar, br, ac, bc - 1); ans -= ST4.rectangle_sum(ar, br - 1, ac, bc - 1); if (ar < xmin && xmax < br - 1 && ac < ymin && ymax < bc - 1){ ans++; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...