#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
const int mx = 2e5 + 5;
struct persistentSegTree{
int idx = 1, root[mx], seg[mx * 31], lc[mx * 31], rc[mx * 31]; set<int> pos[mx];
void add(int r, int c){
pos[r].insert(c);
}
void init(){
for (int i = 0; i < mx; i++){
root[i] = !i ? 0 : root[i - 1];
for (int j : pos[i]) upd(j, 1, root[i]);
}
}
void dup(int &i){
lc[idx] = lc[i];
rc[idx] = rc[i];
seg[idx] = seg[i];
i = idx; idx++;
}
void upd(int p, int val, int &i, int l = 0, int r = 2e5){
dup(i);
if (l == r){ seg[i] += val; return; }
int mid = (l + r) / 2;
if (p <= mid) upd(p, val, lc[i], l, mid);
else upd(p, val, rc[i], mid + 1, r);
seg[i] = seg[lc[i]] + seg[rc[i]];
}
int qry(int ql, int qr, int i, int l = 0, int r = 2e5){
if (qr < l or ql > r or !i) return 0;
if (l >= ql and r <= qr) return seg[i];
int mid = (l + r) / 2;
return qry(ql, qr, lc[i], l, mid) + qry(ql, qr, rc[i], mid + 1, r);
}
int rectQry(int ar, int ac, int br, int bc){
return qry(ac, bc, root[br]) - qry(ac, bc, root[ar - 1]);
}
};
int mnr = 1e9, mxr, mnc = 1e9, mxc; persistentSegTree rivers, nodes, topEdg, leftEdg;
void init(int R, int C, int sr, int sc, int m, string S){
auto addRiver = [&](int r, int c){
rivers.add(r, c);
nodes.add(r, c);
nodes.add(r, c + 1);
nodes.add(r + 1, c);
nodes.add(r + 1, c + 1);
topEdg.add(r, c);
topEdg.add(r + 1, c);
leftEdg.add(r, c);
leftEdg.add(r, c + 1);
mnr = min(mnr, r);
mxr = max(mxr, r);
mnc = min(mnc, c);
mxc = max(mxc, c);
};
addRiver(sr, sc);
for (char c : S){
if (c == 'N') sr--;
if (c == 'S') sr++;
if (c == 'E') sc++;
if (c == 'W') sc--;
addRiver(sr, sc);
}
rivers.init();
nodes.init();
topEdg.init();
leftEdg.init();
}
int colour(int ar, int ac, int br, int bc){
int n = br - ar + 1;
int m = bc - ac + 1;
int C = (ar < mnr and br > mxr and ac < mnc and bc > mxc) ? 2 : 1;
int V = 2 * (n + m) + nodes.rectQry(ar + 1, ac + 1, br, bc);
int E = topEdg.rectQry(ar + 1, ac, br, bc) + leftEdg.rectQry(ar, ac + 1, br, bc) + 2 * (n + m);
int F = E - V + C + 1;
return F - rivers.rectQry(ar, ac, br, bc) - 1;
}
Compilation message
/usr/bin/ld: /tmp/ccbLKAWo.o: in function `main':
grader.cpp:(.text.startup+0xed): undefined reference to `init(int, int, int, int, int, char*)'
collect2: error: ld returned 1 exit status
