Submission #732441

#TimeUsernameProblemLanguageResultExecution timeMemory
732441SanguineChameleonLand of the Rainbow Gold (APIO17_rainbow)C++17
23 / 100
3066 ms225820 KiB
#include "rainbow.h" #include <bits/stdc++.h> using namespace std; struct BIT { set<pair<int, int>> S; vector<map<int, int>> bit; int R, C; void init(int _R, int _C) { R = _R; C = _C; bit.resize(R + 1); } void add(int x, int y) { if (x < 1 || x > R || y < 1 || y > C || S.find({x, y}) != S.end()) { return; } S.insert({x, y}); } void update(int x, int y) { for (int i = x; i <= R; i += i & (-i)) { for (int j = y; j <= C; j += j & (-j)) { bit[i][j]++; } } } void build() { for (auto p: S) { int x = p.first; int y = p.second; update(x, y); } } int get(int x, int y) { int res = 0; for (int i = x; i > 0; i -= i & (-i)) { for (int j = y; j > 0; j -= j & (-j)) { auto it = bit[i].find(j); if (it != bit[i].end()) { res += it->second; } } } return res; } long long get(int lx, int ly, int rx, int ry) { return 1LL * (rx - lx + 1) * (ry - ly + 1) - get(rx, ry) + get(rx, ly - 1) + get(lx - 1, ry) - get(lx - 1, ly - 1); } } V, row_E, col_E, F; int max_X, min_X, max_Y, min_Y; void add(int cx, int cy) { max_X = max(max_X, cx); min_X = min(min_X, cx); max_Y = max(max_Y, cy); min_Y = min(min_Y, cy); V.add(cx, cy); row_E.add(cx - 1, cy); row_E.add(cx, cy); col_E.add(cx, cy - 1); col_E.add(cx, cy); F.add(cx - 1, cy - 1); F.add(cx - 1, cy); F.add(cx, cy - 1); F.add(cx, cy); } void init(int R, int C, int cx, int cy, int M, char *S) { V.init(R, C); row_E.init(R, C); col_E.init(R, C); F.init(R, C); max_X = cx; min_X = cx; max_Y = cy; min_Y = cy; add(cx, cy); for (int i = 0; i < M; i++) { if (S[i] == 'N') { cx--; } if (S[i] == 'E') { cy++; } if (S[i] == 'S') { cx++; } if (S[i] == 'W') { cy--; } add(cx, cy); } V.build(); row_E.build(); col_E.build(); F.build(); } int colour(int lx, int ly, int rx, int ry) { return V.get(lx, ly, rx, ry) - row_E.get(lx, ly, rx - 1, ry) - col_E.get(lx, ly, rx, ry - 1) + F.get(lx, ly, rx - 1, ry - 1) + (lx < min_X && max_X < rx && ly < min_Y && max_Y < ry); }
#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...