/**
* user: ppavic
* fname: Patrik
* lname: Pavić
* task: rainbow
* score: 64.0
* date: 2019-07-10 11:24:28.756490
*/
#include "rainbow.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#define PB push_back
#define X first
#define Y second
using namespace std;
typedef pair < int, int > pt;
const int px[4] = {1, -1, 0, 0};
const int py[4] = {0, 0, 1, -1};
const int OFF = (1 << 18) - 1;
const int N = 2e5 + 500;
map < pt, bool > ima, ima2;
int toc = 0;
struct node{
int cnt;
node *L, *R;
};
int LO, HI, I;
node* NULA;
void update(node* x, int a,int b){
x -> cnt++;
if(a == b) return;
if(I <= (a + b) / 2){
node* tmp = new node();
tmp -> L = x -> L -> L;
tmp -> R = x -> L -> R;
tmp -> cnt = x -> L -> cnt;
x -> L = tmp;
update(x -> L, a, (a + b) / 2);
}
else{
node* tmp = new node();
tmp -> L = x -> R -> L;
tmp -> R = x -> R -> R;
tmp -> cnt = x -> R -> cnt;
x -> R = tmp;
update(x -> R, (a + b) / 2 + 1, b);
}
}
int query(node* x1, node* x2, int a,int b){
if(LO <= a && b <= HI) return (x2 -> cnt) - (x1 -> cnt);
if(a > HI || b < LO) return 0;
return query(x1 -> L, x2 -> L, a, (a + b) / 2) + query(x1 -> R, x2 -> R, (a + b) / 2 + 1, b);
}
struct per_tour{
node* root[N];
void add(vector < pt > &v){
sort(v.begin(), v.end());
//printf("pocelo dodavanje\n");
int j = 0;
root[0] = new node();
root[0] -> L = NULA; root[0] -> R = NULA;
for(int i = 1;i < N;i++){
root[i] = new node();
root[i] -> L = root[i - 1] -> L;
root[i] -> R = root[i - 1] -> R;
root[i] -> cnt = root[i - 1] -> cnt;
for(;j < v.size() && v[j].X == i;j++){
I = v[j].Y;
update(root[i], 0, OFF - 1);
}
}
//printf("gotovo dodavanje\n");
}
int get2d(int x1,int x2,int y1,int y2){
LO = y1, HI = y2;
return query(root[x1 - 1], root[x2], 0, OFF - 1);
}
};
per_tour deg[2], ob, ob2;
void init(int R, int C, int sr, int sc, int M, char *S) {
NULA = new node(); NULA -> L = NULA; NULA -> R = NULA;
int cx = sr, cy = sc;
vector < pt > dod_deg0, dod_deg1, dod_ob, dod_ob2;
ima[{cx, cy}] = 1;
for(int i = 0;i < M;i++){
if(S[i] == 'N') cx--;
if(S[i] == 'S') cx++;
if(S[i] == 'W') cy--;
if(S[i] == 'E') cy++;
ima[{cx, cy}] = 1;
}
for(pair < pt, bool > A : ima){
pt x = A.X; //printf("POLJE %d %d\n", x.X, x.Y);
dod_ob.PB({x.X, x.Y});
ima2[{x.X, x.Y}] = 1;
ima2[{x.X + 1, x.Y}] = 1;
ima2[{x.X, x.Y + 1}] = 1;
ima2[{x.X + 1, x.Y + 1}] = 1;
}
toc = (int)ima2.size();
for(pair < pt, bool > A : ima2){
pt x = A.X; //printf("TOCKA %d %d\n", x.X, x.Y);
dod_ob2.PB({x.X, x.Y});
if(ima2.count({x.X + 1, x.Y}) && (ima.count({x.X, x.Y}) || ima.count({x.X, x.Y - 1})))
dod_deg0.PB({x.X, x.Y});
if(ima2.count({x.X, x.Y + 1}) && (ima.count({x.X - 1, x.Y}) || ima.count({x.X, x.Y})))
dod_deg1.PB({x.X, x.Y});
}
deg[0].add(dod_deg0);
deg[1].add(dod_deg1);
ob.add(dod_ob);
ob2.add(dod_ob2);
}
int colour(int x1, int y1, int x2, int y2) {
x2++, y2++;
int E = 0;
E += deg[0].get2d(x1 , x2 - 1, y1 + 1, y2 - 1);
E += deg[1].get2d(x1 + 1, x2 - 1, y1 , y2 - 1);
E += 2 * (x2 - x1 + y2 - y1);
int kol = ob2.get2d(x1 + 1, x2 - 1, y1 + 1, y2 - 1);
int V = kol + 2 * (x2 - x1 + y2 - y1);
//printf("V = %d E = %d\n", V, E);
int F = E - V + 2;
if(kol == toc) F++;
F--; F -= ob.get2d(x1, x2 - 1, y1, y2 - 1);
return F;
}
