#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define ll long long
const int N = 200005;
struct Node{
Node *l = NULL, *r = NULL;
ll a;
Node* update(int L, int R, int x){
Node* res = new Node();
res -> l = l;
res -> r = r;
res -> a = a;
++res -> a;
if(L == R)
return res;
int m = (L + R) >> 1;
if(x <= m){
if(l == NULL)
l = new Node();
res -> l = l -> update(L, m, x);
} else {
if(r == NULL)
r = new Node();
res -> r = r -> update(m + 1, R, x);
}
return res;
}
ll query(int L, int R, int le, int ri){
if(R < le || L > ri)
return 0;
if(le <= L && R <= ri)
return a;
int m = (L + R) >> 1;
return (l == NULL ? 0 : l -> query(L, m, le, ri)) + (r == NULL ? 0 : r -> query(m + 1, R, le, ri));
}
};
struct Grid{
Node* seg[N];
void build(set<pair<int, int> >& v){
seg[0] = new Node();
auto it = v.begin();
for(int i = 1; i < N; ++i){
seg[i] = seg[i - 1];
while(it != v.end() && it -> ff == i){
seg[i] = seg[i] -> update(1, N, it -> ss);
++it;
}
}
}
ll query(int x1, int y1, int x2, int y2){
if(x1 > x2 || y1 > y2) return 0;
return seg[x2] -> query(1, N, y1, y2) - seg[x1 - 1] -> query(1, N, y1, y2);
}
} riv, dot, lix, liy;
int mnx, mny, mxx, mxy
void init(int R, int C, int sr, int sc, int M, char *S) {
set<pair<int, int> > rivs, dots, lixs, liys;
rivs.insert({sr, sc});
mnx = mxx = sr;
mny = mxy = sc;
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;
rivs.insert({sr, sc});
mnx = min(mnx, sr);
mxx = max(mxx, sr);
mny = min(mny, sc);
mxy = max(mxy, sc);
}
for(auto& a : rivs){
dots.insert({a.ff, a.ss});
dots.insert({a.ff, a.ss + 1});
dots.insert({a.ff + 1, a.ss + 1});
dots.insert({a.ff + 1, a.ss});
lixs.insert({a.ff, a.ss});
lixs.insert({a.ff, a.ss + 1});
liys.insert({a.ff, a.ss});
liys.insert({a.ff + 1, a.ss});
}
riv.build(rivs);
dot.build(dots);
lix.build(lixs);
liy.build(liys);
}
int colour(int x1, int y1, int x2, int y2){
if(x1 < mnx && mxx < x2 && y1 < mny && mxy < y2)
return 1;
return 1 - riv.query(x1, y1, x2, y2) - dot.query(x1 + 1, y1 + 1, x2, y2) + lix.query(x1, y1 + 1, x2, y2) + liy.query(x1 + 1, y1, x2, y2);
}
Compilation message
rainbow.cpp:63:1: error: expected initializer before 'void'
63 | void init(int R, int C, int sr, int sc, int M, char *S) {
| ^~~~
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:100:44: error: 'mxy' was not declared in this scope; did you mean 'mxx'?
100 | if(x1 < mnx && mxx < x2 && y1 < mny && mxy < y2)
| ^~~
| mxx
