/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option
#include<bits/stdc++.h>
using namespace std;
#define all(flg) flg.begin(), flg.end()
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const int mod = 1e9 + 7;
const int maxN = 1 << 20;
int n, m;
int x, y, z, k;
int cnt = 0;
int a[maxN * 26];
struct sextree{
vector<ii> vac;
int sta[200005];
int sz[200005];
void plug(int x, int y){
vac.pb(ii(x, y));
}
void extract(){
sort(all(vac));
vac.resize(unique(all(vac)) - vac.begin());
memset(sz, 0, sizeof(sz));
for(ii pr : vac){
x = pr.fi;
while(x < 200005){
++sz[x];
x += x & -x;
}
}
for1(i, 0, 200005 - 1){
sta[i] = cnt;
cnt += sz[i];
sz[i] = 0;
}
for(ii pr : vac){
x = pr.fi; y = pr.se;
while(x < 200005){
a[sta[x] + sz[x]] = y;
++sz[x];
x += x & -x;
}
}
for1(i, 0, 200005 - 1) sort(a + sta[i], a + sta[i] + sz[i]);
}
int skim(int id, int le, int ri){
--le;
int res = 0;
while(id){
int* sus1 = a + sta[id];
int* sus2 = sus1 + sz[id];
res += upper_bound(sus1, sus2, ri)
- upper_bound(sus1, sus2, le);
id -= (id & -id);
}
return res;
}
int rect(int ar, int ac, int br, int bc){
return skim(br, ac, bc) - skim(ar - 1, ac, bc);
}
};
sextree only, edcol, edrow, cluster;
int repr[128];
int xx[] = {-1, 0, 1, 0};
int yy[] = {0, 1, 0, -1};
// N E S W
int maxr = 0, maxc = 0, minr = maxN, minc = maxN;
void init(int non, int mon, int sn, int sm, int len, string s){
n = non; m = mon;
repr['N'] = 0;
repr['E'] = 1;
repr['S'] = 2;
repr['W'] = 3;
vector<ii> sus;
sus.pb({sn, sm});
for(char cc : s){
sn += xx[repr[cc]];
sm += yy[repr[cc]];
sus.pb({sn, sm});
}
sort(all(sus)); sus.resize(unique(all(sus)) - sus.begin());
for(ii pr : sus){
x = pr.fi; y = pr.se;
// cout << x << " " << y << endl;
maxr = max(maxr, x);
minr = min(minr, x);
maxc = max(maxc, y);
minc = min(minc, y);
only.plug(x, y);
edcol.plug(x, y);
edcol.plug(x + 1, y);
edrow.plug(x, y);
edrow.plug(x, y + 1);
cluster.plug(x + 1, y + 1);
cluster.plug(x + 1, y);
cluster.plug(x, y + 1);
cluster.plug(x, y);
}
only.extract();
edcol.extract();
edrow.extract();
cluster.extract();
}
int colours(int ar, int ac, int br, int bc){
int ans = 0;
if(ar < minr && br > maxr && ac < minc && bc > maxc) ans = 1;
// for(ii pr : edcol.vac) cout << pr.fi << " " << pr.se << endl;
// cout << edcol.rect(ar, ac, br - 1, bc) << endl;
// exit(0);
ans += edcol.rect(ar + 1, ac, br, bc);
ans += edrow.rect(ar, ac + 1, br, bc);
ans -= only.rect(ar, ac, br, bc);
ans -= cluster.rect(ar + 1, ac + 1, br, bc);
++ans;
return ans;
}
Compilation message
rainbow.cpp: In function 'void init(int, int, int, int, int, std::string)':
rainbow.cpp:98:23: warning: array subscript has type 'char' [-Wchar-subscripts]
98 | sn += xx[repr[cc]];
| ^~
rainbow.cpp:99:23: warning: array subscript has type 'char' [-Wchar-subscripts]
99 | sm += yy[repr[cc]];
| ^~
/usr/bin/ld: /tmp/cczFsuav.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
