Submission #544990

#TimeUsernameProblemLanguageResultExecution timeMemory
544990valerikkLand of the Rainbow Gold (APIO17_rainbow)C++17
100 / 100
965 ms122772 KiB
#include "rainbow.h" #include <bits/stdc++.h> using namespace std; struct Fenwick { int n; vector<vector<int> > ys; vector<vector<long long> > f; vector<int> nn; bool built; void fake_add(int x, int y) { assert(!built); for (int i = x + 1; i <= n; i += i & -i) { ys[i].emplace_back(y); } } void build() { assert(!built); for (int i = 0; i <= n; ++i) { sort(ys[i].begin(), ys[i].end()); ys[i].resize(unique(ys[i].begin(), ys[i].end()) - ys[i].begin()); nn[i] = ys[i].size(); f[i].resize(nn[i] + 1); } built = true; } void add(int x, int y) { assert(built); for (int i = x + 1; i <= n; i += i & -i) { for (int j = lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin() + 1; j <= nn[i]; j += j & -j) { f[i][j] += 1; } } } long long get(int x, int y) { assert(built); long long res = 0; for (int i = x; i > 0; i -= i & -i) { for (int j = lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin(); j > 0; j -= j & -j) { res += f[i][j]; } } return res; } long long get(int x1, int y1, int x2, int y2) { return get(x2, y2) - get(x1, y2) - get(x2, y1) + get(x1, y1); } Fenwick(int n = 0) : n(n), ys(n + 1), f(n + 1), nn(n + 1), built(false) {} }; int n, m; int k; vector<pair<int, int> > a; Fenwick fv, fex, fey, ff; int mnx, mny, mxx, mxy; bool blocked(int x, int y) { const auto p = make_pair(x, y); auto it = lower_bound(a.begin(), a.end(), p); return it != a.end() && *it == p; } void init(int R, int C, int sr, int sc, int M, char *S) { n = R; m = C; int x = sr - 1, y = sc - 1; a.emplace_back(x, y); for (int i = 0; i < M; ++i) { if (S[i] == 'N') { --x; } if (S[i] == 'S') { ++x; } if (S[i] == 'E') { ++y; } if (S[i] == 'W') { --y; } a.emplace_back(x, y); } sort(a.begin(), a.end()); a.resize(unique(a.begin(), a.end()) - a.begin()); mnx = numeric_limits<int>::max(); mxx = numeric_limits<int>::min(); mny = numeric_limits<int>::max(); mxy = numeric_limits<int>::min(); vector<pair<int, int>> v, ex, ey, f; for (const auto &[x, y] : a) { mnx = min(mnx, x); mxx = max(mxx, x); mny = min(mny, y); mxy = max(mxy, y); v.emplace_back(x, y); ex.emplace_back(x, y); ey.emplace_back(x, y); f.emplace_back(x, y); if (x > 0) { ex.emplace_back(x - 1, y); f.emplace_back(x - 1, y); } if (y > 0) { ey.emplace_back(x, y - 1); f.emplace_back(x, y - 1); } if (x > 0 && y > 0) { f.emplace_back(x - 1, y - 1); } } sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); sort(ex.begin(), ex.end()); ex.resize(unique(ex.begin(), ex.end()) - ex.begin()); sort(ey.begin(), ey.end()); ey.resize(unique(ey.begin(), ey.end()) - ey.begin()); sort(f.begin(), f.end()); f.resize(unique(f.begin(), f.end()) - f.begin()); fv = {n}; fex = {n}; fey = {n}; ff = {n}; for (const auto &[x, y] : v) { fv.fake_add(x, y); } for (const auto &[x, y] : ex) { fex.fake_add(x, y); } for (const auto &[x, y] : ey) { fey.fake_add(x, y); } for (const auto &[x, y] : f) { ff.fake_add(x, y); } fv.build(); fex.build(); fey.build(); ff.build(); for (const auto &[x, y] : v) { fv.add(x, y); } for (const auto &[x, y] : ex) { fex.add(x, y); } for (const auto &[x, y] : ey) { fey.add(x, y); } for (const auto &[x, y] : f) { ff.add(x, y); } } int colour(int ar, int ac, int br, int bc) { int x1 = ar - 1, y1 = ac - 1, x2 = br, y2 = bc; long long v = (long long) (x2 - x1) * (y2 - y1) - fv.get(x1, y1, x2, y2); long long e = (long long) (x2 - x1 - 1) * (y2 - y1) - fex.get(x1, y1, x2 - 1, y2) + (long long) (x2 - x1) * (y2 - y1 - 1) - fey.get(x1, y1, x2, y2 - 1); long long f = (long long) (x2 - x1 - 1) * (y2 - y1 - 1) - ff.get(x1, y1, x2 - 1, y2 - 1) + (mnx > x1 && mny > y1 && mxx < x2 - 1 && mxy < y2 - 1); if (v == 0) { return 0; } long long c = f - e + v; return (int) c; }
#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...