// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pb push_back
#ifndef safar
#include "rainbow.h"
#endif
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> pii;
template<typename T>
void Unique(vector<T> &V){
sort(all(V));
V.resize(unique(all(V)) - V.begin());
}
int R, C;
vector<pii> Riv, P;
pii corner[] = {{0, 0}, {0, -1}, {-1, 0}, {-1, -1}};
bool Exist(pii X){
return X == *lower_bound(all(Riv), X);
}
vector<int> RE[N], CE[N];
vector<pii> Fen[N];
vector<int> PS[N];
void Add(pii P, int d){
//cerr << "# " << P.F << " " << P.S << " : " << d << '\n';
for(int idx = P.F; idx < N; idx += idx & (-idx))
Fen[idx].pb({P.S, d});
}
void init(int Ri, int Ci, int sr, int sc, int m, string s){
R = Ri; C = Ci;
Riv.resize(m + 1);
Riv[0] = {sr, sc};
for(int i = 1; i <= m; i++){
if(s[i - 1] == 'N') sr --;
if(s[i - 1] == 'S') sr ++;
if(s[i - 1] == 'W') sc --;
if(s[i - 1] == 'E') sc ++;
Riv[i] = {sr, sc};
}
Unique(Riv);
for(auto &X : Riv)
for(auto &del : corner)
if(min(X.F + del.F, X.S + del.S) > 0)
P.pb({X.F + del.F, X.S + del.S});
Unique(P);
//for(auto X : Riv) cerr << X.F << ' ' << X.S << '\n';
Riv.pb({R + 2, C + 2});
for(auto &X : Riv){
if(X.F == R + 2) break;
if(!Exist({X.F, X.S - 1}))
RE[X.F].pb(X.S - 1);
if(!Exist({X.F, X.S + 1}))
RE[X.F].pb(X.S);
if(!Exist({X.F - 1, X.S}))
CE[X.S].pb(X.F - 1);
if(!Exist({X.F + 1, X.S}))
CE[X.S].pb(X.F);
}
int cnt;
for(auto X : P){
cnt = 0;
for(auto &del : corner)
if(Exist({X.F - del.F, X.S - del.S}))
cnt ++;
if(cnt & 1)
Add(X, cnt == 1 ? -1 : 1);
}
for(int i = 1; i < N; i++){
sort(all(Fen[i]));
PS[i].resize(Fen[i].size() + 1, 0);
for(int j = 1; j < (int) Fen[i].size(); j++){
PS[i][j] = PS[i][j - 1] + Fen[i][j - 1].S;
}
}
}
int Get(int x, int y){
int res = 0;
for(; x; x -= x & (-x)){
res += PS[x][upper_bound(all(Fen[x]), pii(y, 2)) - Fen[x].begin()];
}
return res;
}
int colours(int ar, int ac, int br, int bc){
int sum = 0;
if(!Exist({ar, ac})) sum ++;
if(!Exist({ar, bc})) sum ++;
if(!Exist({br, ac})) sum ++;
if(!Exist({br, bc})) sum ++;
if(ar < br && ac < bc){
sum += Get(br - 1, bc - 1);
sum -= Get(ar - 1, bc - 1);
sum -= Get(br - 1, ac - 1);
sum += Get(ar - 1, ac - 1);
}
sum += lower_bound(all(RE[ar]), bc) - upper_bound(all(RE[ar]), ac - 1);
sum += lower_bound(all(RE[br]), bc) - upper_bound(all(RE[br]), ac - 1);
sum += lower_bound(all(CE[ac]), br) - upper_bound(all(CE[ac]), ar - 1);
sum += lower_bound(all(CE[bc]), br) - upper_bound(all(CE[bc]), ar - 1);
//cerr << "! " << sum << '\n';
assert(sum % 4 == 0);
return sum / 4;
}
#ifdef safar
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
init(6, 4, 3, 3, 9, "NWESSWEWS");
//cerr << Get(3, 2) << '\n';
cout << colours(2, 3, 2, 3) << '\n';
cout << colours(3, 2, 4, 4) << '\n';
cout << colours(5, 3, 6, 4) << '\n';
cout << colours(1, 2, 5, 3) << '\n';
return 0;
}
#endif
Compilation message
/tmp/ccvUXABR.o: In function `main':
grader.cpp:(.text.startup+0xcc): undefined reference to `init(int, int, int, int, int, char*)'
grader.cpp:(.text.startup+0x131): undefined reference to `colour(int, int, int, int)'
collect2: error: ld returned 1 exit status
