#include <bits/stdc++.h>
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
const char ch[4] = {'N', 'E', 'W', 'S'};
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, 1, -1, 0};
#define int long long
void mini(int &a, int b) {
if (a > b) a = b;
}
void maxi(int &a, int b) {
if (a < b) a = b;
}
struct node {
int v = 0, l = 0, r = 0;
};
const int L = (int)2e5 + 7;
const int MAX = (int)1e7 + 7;
struct segment_tree {
node t[MAX];
int ver[L + 7];
segment_tree () {};
int cnt = 0;
int build(int l, int r) {
int cur = cnt++;
if (l == r) return cur;
int m = (l + r) >> 1;
t[cur].l = build(l, m);
t[cur].r = build(m + 1, r);
return cur;
}
int lver = 0;
void build() {
ver[0] = build(1, L);
}
int update(int od, int l, int r, int p) {
int cur = cnt++;
t[cur].v = t[od].v + 1;
if (l == r) return cur;
int m = (l + r) >> 1;
if (p <= m) {
t[cur].r = t[od].r;
t[cur].l = update(t[od].l, l, m, p);
} else {
t[cur].l = t[od].l;
t[cur].r = update(t[od].r, m + 1, r, p);
}
return cur;
}
void upd(int vx, int p) {
if (p == -1) {
ver[vx] = ver[vx - 1];
lver = vx;
return ;
}
ver[vx] = update(ver[lver], 1, L, p);
lver = vx;
}
int get(int id, int l, int r, int u, int v) {
if (l > v or r < u) return 0;
if (l >= u and r <= v) return t[id].v;
int m = (l + r) >> 1;
return get(t[id].l, l, m, u, v) + get(t[id].r, m + 1, r, u, v);
}
int get(int x, int y, int u, int v) {
return get(ver[u], 1, L, y, v) - get(ver[x - 1], 1, L, y, v);
}
};
struct CTDL {
const int L = (int)2e5 + 3;
vec<vec<int>> row;
CTDL () {
row.resize(L + 7);
}
segment_tree IT;
void add(int x, int y) {
row[x].push_back(y);
}
void init() {
IT.build();
FOR(i, 1, L) {
if (sz(row[i])) {
unq(row[i]);
}
if (sz(row[i]) == 0) {
IT.upd(i, -1);
} else {
for(int j : row[i]) {
IT.upd(i, j);
}
}
}
}
int get(int x, int y, int u, int v, bool rev) {
if (x > u or y > v) return 0;
int j = IT.get(x, y, u, v);
return rev ? (u - x + 1) * (v - y + 1) - j : j;
}
};
const int N = (int)2e5 + 7;
int n, m;
CTDL orincells, cells, hori, vert; // hori = hang, vert = cot
int minX = INT_MAX, maxX = 0, minY = INT_MAX, maxY = 0;
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R, m = C;
vector<pair<int, int>> rivers;
rivers.push_back(_mp(sr, sc));
for(int i = 0; i < M; ++i) {
for(int j = 0; j < 4; ++j) if (ch[j] == S[i]) {
sr += dx[j], sc += dy[j];
}
rivers.push_back(_mp(sr, sc));
}
unq(rivers);
for(auto cell : rivers) {
int x = cell.first, y = cell.second;
mini(minX, x);
mini(minY, y);
maxi(maxX, x);
maxi(maxY, y);
orincells.add(x, y);
FOR(a, 0, 1)
FOR(b, 0, 1) {
cells.add(x + a, y + b);
}
hori.add(x, y + 1);
hori.add(x + 1, y + 1);
vert.add(x + 1, y + 1);
vert.add(x + 1, y);
}
orincells.init();
cells.init();
hori.init();
vert.init();
}
int colour(int x, int y, int u, int v) {
int R = orincells.get(x, y, u, v, 0);
if (R == 0) return 1;
if (R == (u - x + 1) * (v - y + 1)) return 0;
int h = u - x + 1, w = v - y + 1;
int V = (h + 3) * (w + 3) - cells.get(x + 1, y + 1, u, v, 1);
int E = 4 * (w + 2) + 4 * (h + 2) + 2 * (w - 1) + 2 * (h - 1);
E += hori.get(x + 1, y + 1, u, v + 1, 0) + vert.get(x + 1, y + 1, u + 1, v, 0);
int C = (minX > x and maxX < u and minY > y and maxY < v) ? 2 : 1;
int F = 1 + C - V + E;
return F - (R + 2 * (h + 2) + 2 * (w + 2) - 4 + 1);
}
#ifdef LOCAL
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("main.inp", "r", stdin);
freopen("main.out", "w", stdout);
int r, c, m, q, x, y;
cin >> r >> c >> m >> q >> x >> y;
// string s; cin >> s;
char s[m];
for(int i = 0; i < m; ++i) cin >> s[i];
init(r, c, x, y, m, s);
while (q--) {
int x, y, u, v;
cin >> x >> y >> u >> v;
cout << colour(x, y, u, v) << nl;
}
}
#endif
Compilation message
/usr/bin/ld: /tmp/cc1BEMrC.o: in function `main':
grader.cpp:(.text.startup+0xed): undefined reference to `init(int, int, int, int, int, char*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x167): undefined reference to `colour(int, int, int, int)'
collect2: error: ld returned 1 exit status
