#include <bits/stdc++.h>
using namespace std;
#define M ((L+R)/2)
const int MAXN = 200001;
const int SIZE = 5000001;
struct pres{
set<int> s[MAXN+5];
void add(int x,int y){
s[x].insert(y);
}
int root[MAXN+5];
void bld(){
root[1] = build();
for(int i = 1;i<=MAXN;i++){
root[i+1] = root[i];
for(auto j:s[i]){
root[i+1] = update(j,root[i+1]);
}
}
}
int qry(int l,int r,int L,int R){
if(r>R)return 0;
return query(r,R,root[L+1])-(l?query(r,R,root[l]):0);
}
int l[SIZE], r[SIZE], st[SIZE], NODES = 0;
int n;
int newleaf(int value) {
int p = ++NODES;
l[p] = r[p] = 0; // null
st[p] = value;
return p;
}
int newparent(int lef, int rig) {
int p = ++NODES;
l[p] = lef;
r[p] = rig;
st[p] = st[lef] + st[rig]; // immediately update value from children
return p;
}
int update(int i,int p, int L=1, int R=MAXN) {
if (L == R)return newleaf(st[p]+1);
if (i <= M)return newparent(update(i,l[p], L, M), r[p]);
else return newparent(l[p], update(i,r[p], M + 1, R));
}
int build(int L=1, int R=MAXN) {
if (L == R) return newleaf(0); // construct as leaf
else return newparent(build(L, M),build(M+1,R)); // construct as parent
}
int query(int lq,int rq,int p,int L = 1,int R = MAXN){
if(L>=lq&&R<=rq)return st[p];
if(L>rq||R<lq)return 0;
return query(lq,rq,l[p],L,M)+query(lq,rq,r[p],M+1,R);
}
}ver,edgehorz,edgevert,rivers;
void add_river(int x,int y){
rivers.add(x,y);
ver.add(x,y);
ver.add(x+1,y);
ver.add(x,y+1);
ver.add(x+1,y+1);
edgehorz.add(x,y);
edgehorz.add(x+1,y);
edgevert.add(x,y);
edgevert.add(x,y+1);
}
int mxr ,mnr,mxc,mnc;
void init(int R, int C, int sr, int sc, int MM, char *S) {
add_river(sr,sc);
mxr = sr,mnr = sr,mxc = sc,mnc = sc;
for(int i = 0;i<MM;i++){
if(S[i]=='N')sr--;
if(S[i]=='S')sr++;
if(S[i]=='W')sc--;
if(S[i]=='E')sc++;
add_river(sr,sc);
mxr = max(mxr,sr);
mnr = min(mnr,sr);
mxc = max(mxc,sc);
mnc = min(mnc,sc);
}
rivers.bld();ver.bld();
edgehorz.bld();edgevert.bld();
}
int colour(int ar, int ac, int br, int bc) {
int E = edgehorz.qry(ar + 1, br, ac, bc) + edgevert.qry(ar, br, ac + 1, bc);
int V = ver.qry(ar + 1, br, ac + 1, bc);
int R = rivers.qry(ar, br, ac, bc);
int C = (ar >= mnr || br <= mxr || ac >= mnc || bc <= mxc ? 1 : 2);
return E - V + C - R;
}
int main(){
init(6, 4,
3, 3, 9,
"NWESSWEWS");
cout<<colour(3,2,4,4);
}
Compilation message
rainbow.cpp: In function 'int main()':
rainbow.cpp:96:1: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
96 | "NWESSWEWS");
| ^~~~~~~~~~~
/usr/bin/ld: /tmp/ccS3cBkZ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccOJo4lY.o:rainbow.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
