#include <bits/stdc++.h>
#define pb push_back
//#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define ub upper_bound
using namespace std;
//const int inf = 1e18;
void p(auto A){
for(auto e : A)cout << e << ' ';
cout << '\n';
}
// A = 1 - V + E - F'
// = 1 - 2 + 6 - 3
// = 1 - 4 + 12 - 6
// = 1 - 2 + 3 - 1 = 1
const int MAXQ = 100000;
const int MAXW = 200000;
//const int MAXW = 5;
//const int MAXQ = 2;
struct seg{
array<set<int>, MAXW+5>events;
array<int, MAXW+5> root;
array<int, MAXQ*65> LC, RC, VAL;
int node = 0;
void upd(int prv, int& u, int tl, int tr, int pos, int val){
if(tl > pos || tr < pos)return u=prv, void();
u=++node;
if(tl==tr)return VAL[u]=VAL[prv]+val, void();
int tm=(tl+tr)/2;
upd(LC[prv], LC[u], tl, tm, pos, val);
upd(RC[prv], RC[u], tm+1, tr, pos, val);
VAL[u] = VAL[LC[u]]+VAL[RC[u]];
}
int qer(int u, int tl, int tr, int l, int r){
if(!u)return 0;
if(tl > r || tr < l)return 0;
if(tl >= l && tr <= r)return VAL[u];
int tm = (tl+tr)/2;
int ret = qer(LC[u], tl, tm, l, r)+qer(RC[u], tm+1, tr, l, r);
return ret;
}
void init(){
for(int i = 0; i< events.size(); i++){
if(i)root[i]=root[i-1];
for(auto e : events[i])upd(root[i], root[i], 0, MAXW+3, e, 1);
}
}
int oqer(int x1, int x2, int y1, int y2){
return -qer(root[x1-1], 0, MAXW+3, y1, y2)+qer(root[x2], 0, MAXW+3, y1, y2);
}
}EH, EV, F, V;
int mnx=MAXW+5, mxx=0, mny=MAXW+5, mxy=0;
void add_river(int x, int y){
mnx = min(mnx, x);
mny = min(mny, y);
mxx = max(mxx, x);
mxy = max(mxy, y);
F.events[x].insert(y);
V.events[x].insert(y);
V.events[x+1].insert(y);
V.events[x].insert(y+1);
V.events[x+1].insert(y+1);
EH.events[x].insert(y);
EH.events[x].insert(y+1);
EV.events[x].insert(y);
EV.events[x+1].insert(y);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
add_river(sc, sr);
for(int i = 0; i< M; i++){
if(S[i]=='N')sr--;
if(S[i]=='E')sc++;
if(S[i]=='S')sr++;
if(S[i]=='W')sc--;
add_river(sc, sr);
}
EH.init();
EV.init();
F.init();
V.init();
}
int colour(int ar, int ac, int br, int bc) {
int ret = 1;
if(ar < mny && ac < mnx && br > mxy && bc > mxx)ret++;
ret-=V.oqer(ac+1, bc, ar+1, br);
ret+=EV.oqer(ac+1, bc, ar, br);
ret+=EH.oqer(ac, bc, ar+1, br);
ret-=F.oqer(ac, bc, ar, br);
return ret;
}
void solve(){
int r, c, m, q; cin >> r >> c >> m >> q;
int sr, sc; cin >> sr >> sc;
string S; cin >> S;
init(r, c, sr, sc, m, &S[0]);
for(int i = 0; i< q; i++){
int x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << colour(x1, y1, x2, y2) << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
//cin >> t;
while(t--)solve();
}
Compilation message
rainbow.cpp:15:8: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
15 | void p(auto A){
| ^~~~
rainbow.cpp: In member function 'void seg::init()':
rainbow.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<std::set<int>, 200005>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i = 0; i< events.size(); i++){
| ~^~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccLQxqdd.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc4P64Mc.o:rainbow.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
