// Source: https://dmoj.ca/problem/apio17p1
//
// #include "rainbow.h"
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<int> vi;
#define FOR(i, a, b) for (int i = (a); i<b; i++)
bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }
bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }
const int N = 5e5 + 10;
int cnt = 1;
int seg[100 * N], rightc[100 * N], leftc[100 * N];
struct Segtree {
set<int> need[N];
int roots[N];
void add(int x, int y) {
need[x].insert(y);
}
void build() {
roots[0]=0;
FOR(i, 1, N) {
roots[i]=roots[i-1];
for (auto val: need[i]) update(val, roots[i]);
}
}
void update(int pos, int &node, int l = 0, int r = N) {
if (r <= l) return;
if (pos < l || pos >= r) return;
// cout << l << r << endl;
seg[cnt] = seg[node] + 1; // update
leftc[cnt] = leftc[node];
rightc[cnt] = rightc[node];
node=cnt;
cnt++;
if (l == r-1) return;
int m = (l + r) / 2;
if (pos < m) update(pos, leftc[node], l, m);
if (pos >= m) update(pos, rightc[node], m, r);
}
int query(int node, int ql, int qr, int l, int r) {
if (r <= l) return 0;
if (node == 0) return 0;
if (l == r) return 0;
if (ql <= l && r <= qr) return seg[node];
int acc = 0;
int m = (l + r) / 2;
if (ql < m) acc += query(leftc[node], ql, qr, l, m);
if (qr > m) acc += query(rightc[node], ql, qr, m, r);
return acc;
}
int query(int x1, int y1, int x2, int y2) { // inclusive exclusive
return query(roots[x2-1], y1, y2, 0, N) - query(roots[x1-1], y1, y2, 0, N);
}
} river, edgeh, edgev, vert;
void add(int x, int y) {
// cout << x << y << endl;
river.add(x, y);
edgeh.add(x, y);
edgeh.add(x+1, y);
edgev.add(x, y);
edgev.add(x, y+1);
vert.add(x, y);
vert.add(x+1, y);
vert.add(x, y+1);
vert.add(x+1, y+1);
}
int mnx = N, mny = N;
int mxx = 0, mxy = 0;
void init(int r, int c, int sr, int sc, int m, char* str) {
r = sr;
c = sc;
add(r, c);
FOR(i, 0, m) {
if (str[i] == 'N') r--;
if (str[i] == 'E') c++;
if (str[i] == 'W') c--;
if (str[i] == 'S') r++;
add(r, c);
ckmin(mnx, r);
ckmax(mxx, r);
ckmin(mny, c);
ckmax(mxy, c);
}
river.build();
edgeh.build();
edgev.build();
vert.build();
}
int colour(int ar, int ac, int br, int bc) {
int e = edgeh.query(ar+1, ac, br+1, bc+1) + edgev.query(ar, ac+1, br+1, bc+1);
int r = river.query(ar, ac, br+1, bc+1);
int v = vert.query(ar+1, ac+1, br+1, bc+1);
int c = (ar >= mnx || br <= mxx || ac >= mny || bc <= mxy ? 1 : 2);
// cout << e << ' ' << v << ' ' << c << ' ' << r << endl;
return e-v+c-r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init(6, 4, 3, 3, 9, "NWESSWEWS");
// FOR(x, 1, 10) {
// FOR(y, 1, 10) cout << river.query(river.roots[x], y, y+1, 0, N) - river.query(river.roots[x-1], y, y+1, 0, N) << ' ';
// cout << endl;
// }
// cout << seg[0] << endl;
int a, b, c, d;
while (true) {
cin >> a >> b >> c >> d;
cout << colour(a, b, c, d) << endl;
}
}
Compilation message
rainbow.cpp: In function 'int main()':
rainbow.cpp:139:22: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
139 | init(6, 4, 3, 3, 9, "NWESSWEWS");
| ^~~~~~~~~~~
/usr/bin/ld: /tmp/cctr1Ydk.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccQAxA1g.o:rainbow.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
