#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
long long kaf=(1<<19);
struct segment{
vector<long long>all[maxn];
void add(long long r,long long c){
all[r].push_back(c);
}
struct node{
long long lc,rc,sum;
node(){
lc=rc=sum=0;
}
};
node seg[(1<<20)*20];
long long root[maxn],rt=0,nx=1;
void calc(long long i){
seg[i].sum=seg[seg[i].lc].sum+seg[seg[i].rc].sum;
}
long long ins(long long i,long long l,long long r,long long tl,long long tr,long long w){
if(l>r||l>tr||r<tl||tl>tr){
return i;
}
long long now=nx;
seg[nx]=seg[i];
nx++;
if(l>=tl&&r<=tr){
seg[nx-1].sum+=w;
return nx-1;
}
long long m=(l+r)>>1;
seg[now].lc=ins(seg[now].lc,l,m,tl,tr,w);
seg[now].rc=ins(seg[now].rc,m+1,r,tl,tr,w);
calc(now);
return now;
}
long long get(long long i,long long l,long long r,long long tl,long long tr){
if(l>r||l>tr||r<tl||tl>tr){
return 0;
}
if(l>=tl&&r<=tr){
return seg[i].sum;
}
long long m=(l+r)>>1;
return get(seg[i].lc,l,m,tl,tr)+get(seg[i].rc,m+1,r,tl,tr);
}
long long pors(long long top,long long bot,long long tr,long long tl){
//cout<<"get: "<<get(root[top],0,kaf-1,tl,tr)<<" hehe "<<get(root[bot-1],0,kaf-1,tl,tr)<<endl;
return get(root[top],0,kaf-1,tl,tr)-get(root[bot-1],0,kaf-1,tl,tr);
}
void build(){
for(long long i=0;i<maxn;i++){
sort(all[i].begin(),all[i].end());
all[i].resize(unique(all[i].begin(),all[i].end())-all[i].begin());
for(auto x:all[i]){
rt=ins(rt,0,kaf-1,x,x,1);
}
root[i]=rt;
}
}
}segv,segeo,segea,segr;
long long mxr=-1,mxc=-1,mnr=maxn+10,mnc=maxn+10;
void add(long long r,long long c){
//cout<<"addy: "<<r<<" "<<c<<endl;
mnr=min(mnr,r);
mxr=max(mxr,r);
mnc=min(mnc,c);
mxc=min(mnc,c);
segv.add(r,c);
segv.add(r,c+1);
segv.add(r+1,c);
segv.add(r+1,c+1);
segeo.add(r,c);
segeo.add(r+1,c);
segea.add(r,c);
segea.add(r,c+1);
segr.add(r,c);
}
void build(){
segv.build();
segeo.build();
segea.build();
segr.build();
}
void init(long long R, long long C, long long sr, long long sc, long long M, char *S) {
add(sr,sc);
for(long long i=0;i<M;i++){
if(S[i]=='N'){
sr--;
}
else if(S[i]=='S'){
sr++;
}else if(S[i]=='E'){
sc++;
}else{
sc--;
}
add(sr,sc);
}
build();
}
long long colour(long long ar, long long ac, long long br, long long bc) {
long long v=segv.pors(br,ar+1,bc,ac+1)+(br-ar+2)*2+(bc-ac)*2;
long long c=1;
long long e=segeo.pors(br,ar+1,bc,ac)+segea.pors(br,ar,bc,ac+1)+(br-ar+1)*2+(bc-ac+1)*2;
long long r=segr.pors(br,ar,bc,ac);
if(mnr>ar&&mxr<br&&mnc>ac&&mxc<bc){
c++;
}
long long res=e-v+1+c-r-1;
return res;
}
Compilation message
/usr/bin/ld: /tmp/ccbApxNd.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
