Submission #1276379

#TimeUsernameProblemLanguageResultExecution timeMemory
1276379LucaLucaMLand of the Rainbow Gold (APIO17_rainbow)C++20
50 / 100
785 ms51320 KiB
#include "rainbow.h" #include <iostream> #include <vector> #include <cassert> #include <algorithm> #include <set> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("Ofast") const int MAXN = 1000 + 7; using ll = long long; struct Fenwick2D { // ah wait defapt pot face doar niste cautari binare std::set<std::pair<int, int>> cells; std::vector<int> ys[MAXN + 1]; void add(int x, int y) { if (cells.count({x, y})) { // sa am grija sa nu inserez aceeasi pozitie de mai multe ori return; } cells.insert({x, y}); x++; for (int i = x; i <= MAXN; i += i & -i) { ys[i].push_back(y); } } void build() { for (int i = 1; i <= MAXN; i++) { ys[i].push_back(0); ys[i].push_back(MAXN + 7); std::sort(ys[i].begin(), ys[i].end()); } } int query(int x, int y) { x++; int ret = 0; for (int i = x; i > 0; i -= i & -i) { ret += std::upper_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin(); } return ret; } int query(int x1, int y1, int x2, int y2) { return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1); } }; namespace { int minX, maxX, minY, maxY; Fenwick2D vert, horizontalEdges, verticalEdges, boxes; }; void init(int R, int C, int sr, int sc, int M, char *S) { int x = sr, y = sc; minX = R + 1; minY = C + 1; maxX = 0; maxY = 0; auto add = [&](int x, int y) { minX = std::min(minX, x); maxX = std::max(maxX, x); minY = std::min(minY, y); maxY = std::max(maxY, y); vert.add(x, y); horizontalEdges.add(x, y); horizontalEdges.add(x, y - 1); verticalEdges.add(x, y); verticalEdges.add(x - 1, y); boxes.add(x, y); boxes.add(x, y - 1); boxes.add(x - 1, y); boxes.add(x - 1, y - 1); }; add(x, y); for (int i = 0; i < M; i++) { if (S[i] == 'N') { x--; } else if (S[i] == 'S') { x++; } else if (S[i] == 'W') { y--; } else { y++; } add(x, y); } vert.build(); horizontalEdges.build(); verticalEdges.build(); boxes.build(); } int colour(int x1, int y1, int x2, int y2) { ll V = (ll) (x2 - x1 + 1) * (y2 - y1 + 1) - vert.query(x1, y1, x2, y2); ll E = 0; E += (ll) (x2 - x1 + 1) * (y2 - y1) - horizontalEdges.query(x1, y1, x2, y2 - 1); E += (ll) (x2 - x1) * (y2 - y1 + 1) - verticalEdges.query(x1, y1, x2 - 1, y2); ll F = (ll) (x2 - x1) * (y2 - y1) - boxes.query(x1, y1, x2 - 1, y2 - 1); F++; if (x1 < minX && maxX < x2 && y1 < minY && maxY < y2) { F++; } // V + F = E + C + 1 (cred) return V + F - E - 1; }
#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...