#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#ifndef BALBIT
#include "rainbow.h"
#endif
int n,m;
vector<pii> pts;
vector<pii> linev, lineh, face; // record top-left for all
bool H(pii &p) {
return *lower_bound(ALL(pts), p) == p;
}
const int maxn = 2e5+5;
struct PBIT{
vector<vector<pii> > s;
void MO(int e, int v, int tm) {
for (++e; e<maxn; e += e&-e) {
s[e].pb({tm, s[e].back().s + v});
}
}
int QU(int e, int tm) {
int re = 0;
for (++e; e>0; e -= e&-e) {
re += prev(upper_bound(ALL(s[e]), pii{tm,10000000})) -> s;
}
return re;
}
int GT(int r1, int r2, int c1, int c2) {
return QU(c2,r2) + QU(c1-1,r1-1) - QU(c2, r1-1) - QU(c1-1, r2);
}
PBIT (vector<pii> v){
s.resize(maxn+1, {{-1,0}});
// sorted by r
for (pii p : v) {
if (p.f >=1 && p.s >=1)
MO(p.s, 1, p.f);
}
}
PBIT(){}
};
PBIT bitV, bitEv, bitEh, bitF;
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R, m = C;
pts.pb({sr, sc});
for (int i = 0; i<M; ++i) {
if (S[i] == 'N') {
--sr;
}
if (S[i] == 'S') {
++sr;
}
if (S[i] == 'E') {
++sc;
}
if (S[i] == 'W') {
--sc;
}
pts.pb({sr, sc});
}
sort(ALL(pts));
pts.resize(unique(ALL(pts)) - pts.begin());
for (pii p : pts) {
linev.pb({p.f-1, p.s});
linev.pb({p.f, p.s});
lineh.pb({p.f, p.s-1});
lineh.pb({p.f, p.s});
face.pb({p.f-1, p.s-1});
face.pb({p.f, p.s-1});
face.pb({p.f-1, p.s});
face.pb({p.f, p.s});
}
bug("HI");
sort(ALL(linev));
sort(ALL(lineh));
sort(ALL(face));
linev.resize(unique(ALL(linev)) - linev.begin());
lineh.resize(unique(ALL(lineh)) - lineh.begin());
face.resize(unique(ALL(face)) - face.begin());
bug("HI");
bitV = PBIT(pts);
bitF = PBIT(face);
bitEh = PBIT(lineh);
bitEv = PBIT(linev);
}
int r1, c1, r2, c2;
int colour(int R1, int C1, int R2, int C2) {
tie(r1,c1,r2,c2) = tie(R1,C1,R2,C2);
ll rd = R2-R1+1, cd = C2-C1+1;
ll V = rd * cd -bitV.GT(r1,r2,c1,c2);
ll F = (rd - 1) * (cd - 1) - bitF.GT(r1,r2-1,c1,c2-1);
ll E = (rd-1) * cd + (rd) * (cd-1) - (bitEh.GT(r1,r2,c1,c2-1) + bitEv.GT(r1,r2-1,c1,c2));
bug(V, E, F);
return V-E+F;
}
#ifdef BALBIT
signed main(){
IOS();
init(6,4,3,3,9,"NWESSWEWS");
bug(colour(2, 3, 2, 3));
bug(colour(3, 1, 6, 4));
bug(colour(5, 3, 6, 6));
bug(colour(1, 2, 5, 3));
}
#endif
Compilation message
rainbow.cpp:58:2: error: stray '\302' in program
if (p.f >=1 && p.s >=1)
^
rainbow.cpp:58:3: error: stray '\240' in program
if (p.f >=1 && p.s >=1)
^
rainbow.cpp:58:5: error: stray '\302' in program
if (p.f >=1 && p.s >=1)
^
rainbow.cpp:58:6: error: stray '\240' in program
if (p.f >=1 && p.s >=1)
^
rainbow.cpp:58:8: error: stray '\302' in program
if (p.f >=1 && p.s >=1)
^
rainbow.cpp:58:9: error: stray '\240' in program
if (p.f >=1 && p.s >=1)
^
rainbow.cpp:58:11: error: stray '\302' in program
if (p.f >=1 && p.s >=1)
^
rainbow.cpp:58:12: error: stray '\240' in program
if (p.f >=1 && p.s >=1)
^
rainbow.cpp:58:14: error: stray '\302' in program
if (p.f >=1 && p.s >=1)
^
rainbow.cpp:58:15: error: stray '\240' in program
if (p.f >=1 && p.s >=1)
^
rainbow.cpp:58:17: error: stray '\302' in program
if (p.f >=1 && p.s >=1)
^
rainbow.cpp:58:18: error: stray '\240' in program
if (p.f >=1 && p.s >=1)
^
