제출 #250874

#제출 시각아이디문제언어결과실행 시간메모리
250874receed무지개나라 (APIO17_rainbow)C++14
12 / 100
489 ms70628 KiB
#include "rainbow.h" #include <iostream> #include <iomanip> #include <cstdio> #include <vector> #include <algorithm> #include <cmath> #include <cstring> #include <cassert> #include <string> #include <set> #include <map> #include <random> #include <bitset> #include <string> #include <unordered_set> #include <unordered_map> #include <deque> #include <queue> #define rep(i, n) for (int i = 0; i < (n); i++) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; using ll = long long; using ul = unsigned long long; using ld = long double; const int N = 1 << 18, M = N * 40; int tr[M], lv[M], rv[M], sz = 1, rt[N]; set<pair<int, int>> ss, ts; map<int, vector<int>> mh, mv; int lx, rx, ly, ry; int add(int v, int p, int x, int l=0, int r=N) { int cv = sz++; tr[cv] = tr[v] + x; if (r - l == 1) lv[cv] = rv[cv] = -1; else if (p < (l + r) / 2) { lv[cv] = add(lv[v], p, x, l, (l + r) / 2); rv[cv] = rv[v]; } else { lv[cv] = lv[v]; rv[cv] = add(rv[v], p, x, (l + r) / 2, r); } return cv; } int sum(int v, int cl, int cr, int l=0, int r=N) { if (v == -1 || cr <= l || r <= cl) return 0; if (cl <= l && r <= cr) return tr[v]; return sum(lv[v], cl, cr, l, (l + r) / 2) + sum(rv[v], cl, cr, (l + r) / 2, r); } void init(int r, int c, int sr, int sc, int m, char *s) { lx = rx = r; ly = ry = c; ss.insert({sr, sc}); rep(i, m) { if (s[i] == 'N') sr--; else if (s[i] == 'S') sr++; else if (s[i] == 'W') sc--; else sc++; lx = min(lx, sr); rx = max(rx, sr); ly = min(ly, sc); ry = max(ry, sc); ss.insert({sr, sc}); } for (auto &p : ss) { ts.insert(p); if (p.first > 1) { ts.insert({p.first - 1, p.second}); if (p.second > 1) ts.insert({p.first - 1, p.second - 1}); } if (p.second > 1) ts.insert({p.first, p.second - 1}); } int crt = 0, ls = 0; for (auto &p : ts) { while (ls < p.first) rt[ls++] = crt; int val = -1; if (ss.count(p)) { val += 1; if (!ss.count({p.first, p.second + 1})) mh[p.first].push_back(p.second); if (!ss.count({p.first + 1, p.second})) mv[p.second].push_back(p.first); } else { if (ss.count({p.first, p.second + 1})) val++; if (ss.count({p.first + 1, p.second})) val++; } crt = add(crt, p.second, val); } for (auto &p : mh) sort(all(p.second)); for (auto &p : mv) sort(all(p.second)); } int colour(int ar, int ac, int br, int bc) { ll ans = 1 + sum(rt[br - 1], ac, bc) - sum(rt[ar - 1], ac, bc); // cout << ans << '\n'; if (mh.count(br)) ans += lower_bound(all(mh[br]), bc) - lower_bound(all(mh[br]), ac); if (mv.count(bc)) ans += lower_bound(all(mv[bc]), br) - lower_bound(all(mv[bc]), ar); if (ss.count({br, ac})) ans--; if (ss.count({ar, bc})) ans--; if (ss.count({br, bc})) ans++; if (ar < lx && rx < br && ac < ly && ry < bc) 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...