#ifndef CHEISSMART
#include "rainbow.h"
#endif
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
cerr << to_string(h);
if(sizeof ...(t)) cerr << ", ";
DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif
const int INF = 1e9 + 7, N = 2e5 + 7;
string dir = "NSWE";
int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
int R, C;
struct qry_2D {
struct node {
node *l, *r;
int sum;
node(int _sum = 0) {
sum = _sum;
l = r = nullptr;
}
node(node* _l, node* _r) {
l = _l, r = _r;
sum = (l ? l -> sum : 0) + (r ? r -> sum : 0);
}
};
node* p[N];
node* add(node* t, int pos, int tl = 0, int tr = C) {
if(!t) t = new node();
if(tr - tl == 1) return new node(1 + t -> sum);
int tm = (tl + tr) / 2;
if(pos < tm) return new node(add(t -> l, pos, tl, tm), t -> r);
else return new node(t -> l, add(t -> r, pos, tm, tr));
}
int qry(node* t, int l, int r, int tl = 0, int tr = C) {
if(!t) return 0;
if(l <= tl && tr <= r) return t -> sum;
int tm = (tl + tr) / 2, ans = 0;
if(l < tm) ans += qry(t -> l, l, r, tl, tm);
if(r > tm) ans += qry(t -> r, l, r, tm, tr);
return ans;
}
vi todo[N];
void add(int x, int y) {
todo[x].PB(y);
}
int qry(int xl, int xr, int yl, int yr) { // [xl, xr] x [yl, yr]
if(xl > xr || yl > yr) return 0;
int ans = 0;
for(int i = xl; i <= xr; i++) {
for(int y:todo[i])
if(yl <= y && y <= yr)
ans++;
}
assert(ans == qry(p[xr], yl, yr + 1) - qry((xl ? p[xl - 1] : nullptr), yl, yr + 1));
return qry(p[xr], yl, yr + 1) - qry((xl ? p[xl - 1] : nullptr), yl, yr + 1);
}
void build() {
node* lst = nullptr;
for(int i = 0; i < R; i++) {
for(int y:todo[i])
lst = add(lst, y);
p[i] = lst;
}
}
} cell, node, hor, ver;
#define do_once static set<pi> vis; if(vis.count({r, c})) return; vis.insert({r, c});
void init(int R, int C, int sr, int sc, int M, char *S) {
::R = R + 1, ::C = C + 1;
auto mark_node = [&] (int r, int c) {
do_once
node.add(r, c);
};
auto mark_hor = [&] (int r, int c) {
do_once
hor.add(r, c);
};
auto mark_ver = [&] (int r, int c) {
do_once
ver.add(r, c);
};
auto arrive = [&] (int r, int c) {
do_once
cell.add(r, c);
mark_ver(r, c), mark_hor(r, c);
mark_ver(r, c - 1);
mark_hor(r - 1, c);
mark_node(r, c), mark_node(r - 1, c), mark_node(r, c - 1), mark_node(r - 1, c - 1);
};
arrive(sr, sc);
for(int i = 0; i < M; i++) {
int k = find(ALL(dir), S[i]) - dir.begin();
sr += di[k], sc += dj[k];
arrive(sr, sc);
}
cell.build(), ver.build(), hor.build(), node.build();
}
int colour(int ar, int ac, int br, int bc) {
// F = C + E - V
ll V = (ll) (br - ar + 2) * (bc - ac + 2);
ll E = (br - ar + 1) * 2 + (bc - ac + 1) * 2
+ ver.qry(ar, br, ac, bc - 1)
+ hor.qry(ar, br - 1, ac, bc);
ll bad_nodes = node.qry(ar, br - 1, ac, bc - 1);
if(node.qry(ar - 1, ar - 1, ac - 1, bc) || node.qry(br, br, ac - 1, bc) ||
node.qry(ar - 1, br, ac - 1, ac - 1) || node.qry(ar - 1, br, bc, bc)) {
bad_nodes += (br - ar + 2) * 2 + (bc - ac + 2) * 2 - 4;
}
ll C = V - bad_nodes + (bad_nodes ? 1 : 0);
ll F = C + E - V;
F -= cell.qry(ar, br, ac, bc);
return F;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
19276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19056 KB |
Output is correct |
| 2 |
Correct |
12 ms |
19112 KB |
Output is correct |
| 3 |
Execution timed out |
3077 ms |
262076 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19020 KB |
Output is correct |
| 2 |
Correct |
790 ms |
432076 KB |
Output is correct |
| 3 |
Correct |
730 ms |
410448 KB |
Output is correct |
| 4 |
Correct |
776 ms |
423584 KB |
Output is correct |
| 5 |
Correct |
594 ms |
319768 KB |
Output is correct |
| 6 |
Incorrect |
156 ms |
97016 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
19276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
19276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
