// And you curse yourself for things you never done
#include<bits/stdc++.h>
#include "rainbow.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
struct Segment{
vector<int> v[4 * maxn], L[4 * maxn], R[4 * maxn], tdo[maxn];
set<pii> st;
void restart(){
for(int i = 0; i < maxn; i++)
tdo[i].clear();
st.clear();
}
void add(int x, int y){
if(st.count({x, y}))
return;
st.insert({x, y});
tdo[x].PB(y);
}
void build(int l = 0, int r = maxn, int id = 1){
if(r-l == 1){
v[id] = tdo[l];
sort(v[id].begin(), v[id].end());
return;
}
int mid = (l+r) >> 1;
build(l, mid, 2*id);
build(mid, r, 2*id+1);
int pt1 = 0, pt2 = 0;
v[id].clear(), L[id].clear(), R[id].clear();
while(pt1 < sz(v[2*id]) || pt2 < sz(v[2*id+1])){
L[id].PB(pt1), R[id].PB(pt2);
if(pt2 == sz(v[2*id+1]) || (pt1 != sz(v[2*id]) && v[2*id][pt1] <= v[2*id+1][pt2]))
v[id].PB(v[2*id][pt1++]);
else
v[id].PB(v[2*id+1][pt2++]);
}
L[id].PB(pt1), R[id].PB(pt2); // important
}
int ask(int f, int s, int ff, int ss, int l = 0, int r = maxn, int id = 1, int ptl = -1, int ptr = -1){
if(id == 1){
ptl = lower_bound(v[1].begin(), v[1].end(), ff) - v[1].begin();
ptr = lower_bound(v[1].begin(), v[1].end(), ss) - v[1].begin();
}
if(ptl >= ptr || r <= f || s <= l || ss <= ff || s <= f || r <= l)
return 0;
if(f <= l && r <= s)
return ptr - ptl;
int mid = (l+r) >> 1;
return ask(f, s, ff, ss, l, mid, 2*id, L[id][ptl], L[id][ptr]) + ask(f, s, ff, ss, mid, r, 2*id+1, R[id][ptl], R[id][ptr]);
}
};
Segment s1, s2, s3, s4;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int MX, mx, MY, my;
void init(int N, int M, int x, int y, int n, string s){
s1.restart(), s2.restart(), s3.restart(), s4.restart();
auto ok = [&](int x, int y){
return x >= 0 && y >= 0 && x < N && y < M;
};
auto add = [&](int x, int y){
s1.add(x, y);
if(ok(x-1, y))
s2.add(x-1, y);
if(ok(x+1, y))
s2.add(x, y);
if(ok(x, y-1))
s3.add(x, y-1);
if(ok(x, y+1))
s3.add(x, y);
if(ok(x-1, y-1))
s4.add(x-1, y-1);
if(ok(x-1, y+1))
s4.add(x-1, y);
if(ok(x+1, y-1))
s4.add(x, y-1);
if(ok(x+1, y+1))
s4.add(x, y);
};
--x, --y;
add(x, y);
MX = mx = x, MY = my = y;
for(char c : s){
if(c == 'N')
x--;
if(c == 'W')
y--;
if(c == 'S')
x++;
if(c == 'E')
y++;
add(x, y);
MX = max(MX, x);
mx = min(mx, x);
MY = max(MY, y);
my = min(my, y);
}
s1.build(), s2.build(), s3.build(), s4.build();
}
int colours(int x, int y, int xx, int yy){
--x, --y;
if(x < mx && MX < xx-1 && y < my && MY < yy-1)
return 1;
int A = (xx-x) * (yy-y) - s1.ask(x, xx, y, yy);
int B = (yy-y) * (xx-x-1) - s2.ask(x, xx-1, y, yy);
int C = (xx-x) * (yy-y-1) - s3.ask(x, xx, y, yy-1);
int D = (xx-x-1) * (yy-y-1) - s4.ask(x, xx-1, y, yy-1);
return A + D - B - C;
}
Compilation message
/tmp/ccaPESbk.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
