#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};
void mini(int &a, int b) {
if (a > b) a = b;
}
void maxi(int &a, int b) {
if (a < b) a = b;
}
vector<pair<int, int>> points;
struct CTDL {
const int L = (int)1e3 + 7;
vec<vec<int>> cnt;
CTDL () {
cnt.resize(L);
for(int i = 0; i < L; ++i)
cnt[i].resize(L);
}
void add(int x, int y) {
assert(x > 0 and y > 0);
cnt[x][y] = 1;
}
int get(int x, int y, int u, int v, bool rev) {
if (x > u or y > v) return 0;
int j = (u - x + 1) * (v - y + 1);
int res = 0;
FOR(i, x, u) FOR(j, y, v)
res += cnt[i][j];
return rev ? (j - res) : res;
}
};
const int N = (int)2e5 + 7;
int n, m;
vector<int> row[N], col[N];
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, string 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) {
orincells.add(cell.fi, cell.se);
FOR(a, 0, 1)
FOR(b, 0, 1) {
points.emplace_back(cell.first + a, cell.second + b);
}
hori.add(cell.fi, cell.se + 1);
hori.add(cell.fi + 1, cell.se + 1);
vert.add(cell.fi + 1, cell.se + 1);
vert.add(cell.fi + 1, cell.se);
}
unq(points);
for(auto cell : points) {
mini(minX, cell.first);
mini(minY, cell.second);
maxi(maxX, cell.first);
maxi(maxY, cell.second);
cells.add(cell.first, cell.second);
}
}
int get(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);
// cerr << "\n\n";
// cerr << "border: " << E << nl;
// cerr << "h, w: " << h << ' ' << w << nl;
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;
// cerr << V << ' ' << E << ' ' << C << ' ' << F << ' ' << R << nl;
return F - (R + 2 * (h + 2) + 2 * (w + 2) - 4 + 1);
}
//#define LOCAL
#ifdef LOCAL
int 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;
init(r, c, x, y, m, s);
while (q--) {
int x, y, u, v;
cin >> x >> y >> u >> v;
cout << get(x, y, u, v) << nl;
}
}
#endif
Compilation message
/usr/bin/ld: /tmp/ccUPSciN.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
