#include "rainbow.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define m_p make_pair
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
const int N=200'000;
int n,m;
struct dsu{
int p[N],sz[N];
void make(int v){
p[v]=v;
sz[v]=1;
}
int get(int v){
return p[v]=(p[v]!=v?get(p[v]):v);
}
bool mg(int a,int b){
a=get(a),b=get(b);
if(a==b) return 0;
if(sz[a]>sz[b]) swap(a,b);
p[a]=b;sz[b]+=sz[a];
return 1;
}
};
dsu in;
map<pii,int> plased;
bool is[51][51];
char dx[4]={'W','E','N','S'};
int tx[4]={0,0,-1,1};
int ty[4]={-1,1,0,0};
vec<pii> go[2];
vec<int> cl[2];
void init(int R, int C, int sr, int sc, int M, char *S) {
n=R,m=C;
--sr;--sc;
plased[{sr,sc}]=1;
if(n<=50 && m<=50)
is[sr][sc]=1;
if(n<=2)
cl[sr].pb(sc);
for(int i=0;i<M;i++){
// cout<<"P "<<S[i]<<endl;
for(int j=0;j<4;j++){
if(dx[j]==S[i]){
sr+=tx[j];sc+=ty[j];
// cout<<"E "<<endl;
}
}
plased[{sr,sc}]=1;
// go[sr].pb
if(n<=2)
cl[sr].pb(sc);
// cout<<"ALO "<<sr+1<<' '<<sc+1<<endl;
if(n<=50 && m<=50)
is[sr][sc]=1;
}
if(n<=50 && m<=50){
}
else if(n==2){
for(int i=0;i<2;i++){
vec<pii> wow;
int last=-1;
sort(all(cl[i]));
for(auto &z : cl[i]){
if(z-last-1>=0)
wow.pb({last+1,z-1});
last=z;
}
go[i]=wow;
}
}
else{
}
}
int ask1(int x,int x1,int y,int y1){
// if(x1==y1 || y==y1) return 0;
// --x1;--y1;
--x;--x1;--y;--y1;
for(int i=x;i<=x1;i++){
for(int j=y;j<=y1;j++){
if(!is[i][j]){
in.make(i*m+j);
// cout<<"IN "<<i<<' '<<j<<endl;
}
}
}
int ans=0;
for(int i=x;i<=x1;i++){
for(int j=y;j<=y1;j++){
if(is[i][j]) continue;
// cout<<"N "<<endl;
for(int t=0;t<4;t++){
int ni=i+tx[t],nj=j+ty[t];
if(ni>=x && ni<=x1 && nj>=y && nj<=y1 && !is[ni][nj])
in.mg(i*m+j,ni*m+nj);
}
}
}
for(int i=x;i<=x1;i++){
for(int j=y;j<=y1;j++){
if(is[i][j]) continue;
// cout<<"HERE "<<i<<' '<<j<<' '<<endl;
if(in.get(i*m+j)==(i*m+j))
ans++;
}
}
return ans;
}
int ask2(int x,int x1,int y,int y1){
if(x==x1){
auto l=lower_bound(all(go[x]),m_p(y,y-1))-go[x].begin();
if(l && go[x][l-1].s>=y) l--;
auto r=lower_bound(all(go[x]),m_p(y1+1,y1-1))-go[x].begin();
if(r==sz(go[r]) || go[x][r].f>y1) --r;
return r-l+1;
}
else{
int sh=cl[0].lower_bound(y)-cl[0].begin();
int sh1=cl[1].lower_bound(y)-cl[1].begin();
int ok=0;
if(sh!=sz(cl[0]) && sh1!=sz(cl[1]) && max(cl[0][sh],cl[1][sh1])<=y1) ok=0;
else ok=1;
return ask2(0,0,y,y1)+ask2(1,1,y,y1)-(!plased[{0,y}] && !plased[{1,y}])
-((!plased[{0,y1}] && !plased[{1,y1}]))+ok;
}
}
int colour(int ar, int ac, int br, int bc) {
if(n<=50 && m<=50)
return ask1(ar,br,ac,bc);
if(n==2)
return ask2(ar,br,ac,bc);
return 0;
}
Compilation message
rainbow.cpp: In function 'int ask2(int, int, int, int)':
rainbow.cpp:137:22: error: 'class std::vector<int>' has no member named 'lower_bound'
137 | int sh=cl[0].lower_bound(y)-cl[0].begin();
| ^~~~~~~~~~~
rainbow.cpp:138:23: error: 'class std::vector<int>' has no member named 'lower_bound'
138 | int sh1=cl[1].lower_bound(y)-cl[1].begin();
| ^~~~~~~~~~~
