#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
class SegmentTree {
private:
struct Node {
int val = 0;
Node *lc = nullptr;
Node *rc = nullptr;
};
int sz;
Node *root = nullptr;
void Pull(Node* &n) {
n->val = 0;
if (n->lc != nullptr) n->val += n->lc->val;
if (n->rc != nullptr) n->val += n->rc->val;
}
void Update(Node* &n, int tl, int tr, int p, int x) {
if (n == nullptr) n = new Node();
if (tl == tr) return void(n->val = x);
int mid = (tl + tr) / 2;
if (p <= mid) {
Update(n->lc, tl, mid, p, x);
} else {
Update(n->rc, mid + 1, tr, p, x);
}
return Pull(n);
}
int Query(Node* &n, int tl, int tr, int l, int r) {
if (n == nullptr) return 0;
if (r < tl || tr < l || tl > tr || l > r) return 0;
if (l <= tl && tr <= r) return n->val;
int mid = (tl + tr) / 2;
return Query(n->lc, tl, mid, l, r) +
Query(n->rc, mid + 1, tr, l, r);
}
public:
SegmentTree() {}
SegmentTree(int sz) : sz(sz) {}
void Update(int p, int x) {
return Update(root, 0, sz, p, x);
}
int Query(int l, int r) {
return Query(root, 0, sz, l, r);
}
};
class RangeTree {
private:
struct Node {
SegmentTree seg;
Node *lc = nullptr;
Node *rc = nullptr;
Node(int sz) : seg(sz) {}
};
int sx, sy;
Node *root = nullptr;
void Pull(Node* &n, int pos) {
int val = 0;
if (n->lc != nullptr) val += n->lc->seg.Query(pos, pos);
if (n->rc != nullptr) val += n->rc->seg.Query(pos, pos);
n->seg.Update(pos, val);
}
void Update(Node* &n, int tl, int tr, int p, int q, int x) {
if (n == nullptr) n = new Node(sy);
if (tl == tr) return void(n->seg.Update(q, x));
if (tl == tr) return;
int mid = (tl + tr) / 2;
if (p <= mid) {
Update(n->lc, tl, mid, p, q, x);
} else {
Update(n->rc, mid + 1, tr, p, q, x);
}
return Pull(n, q);
}
int Query(Node* &n, int tl, int tr, int l, int r, int d, int u) {
if (n == nullptr) return 0;
if (r < tl || tr < l || tl > tr || l > r) return 0;
if (l <= tl && tr <= r) return n->seg.Query(d, u);
int mid = (tl + tr) / 2;
return Query(n->lc, tl, mid, l, r, d, u) +
Query(n->rc, mid + 1, tr, l, r, d, u);
}
public:
RangeTree() {}
RangeTree(int sx, int sy) : sx(sx), sy(sy) {}
void Update(int p, int q, int x) {
return Update(root, 0, sx, p, q, x);
}
int Query(int l, int r, int d, int u) {
return Query(root, 0, sx, l, r, d, u);
}
};
// V - E + F = 2
// Vertices = 4 suares points aroud river cells
// Edges = borders around river cells
// Faces = land components + number of river cells
RangeTree river_cells; // keeps V - E + F, scaled by 2
int minr, maxr, minc, maxc;
void init(int R, int C, int sr, int sc, int M, char *S) {
river_cells = RangeTree(2 * R + 5, 2 * C + 5);
auto Update = [&](int x, int y) { // cell (x, y) is a river cell
// Vertices
river_cells.Update(2 * x - 1, 2 * y - 1, 1);
river_cells.Update(2 * x - 1, 2 * y + 1, 1);
river_cells.Update(2 * x + 1, 2 * y - 1, 1);
river_cells.Update(2 * x + 1, 2 * y + 1, 1);
// Edges
river_cells.Update(2 * x - 1, 2 * y, -1);
river_cells.Update(2 * x + 1, 2 * y, -1);
river_cells.Update(2 * x, 2 * y - 1, -1);
river_cells.Update(2 * x, 2 * y + 1, -1);
// Faces
river_cells.Update(2 * x, 2 * y, 1);
};
minr = maxr = sr;
minc = maxc = sc;
Update(sr, sc);
for (int i = 0; i < M; i++) {
if (S[i] == 'N') sr--;
if (S[i] == 'S') sr++;
if (S[i] == 'W') sc--;
if (S[i] == 'E') sc++;
Update(sr, sc);
minr = min(minr, sr);
minc = min(minc, sc);
maxr = max(maxr, sr);
maxc = max(maxc, sc);
}
minr--;
maxr++;
minc--;
maxc++;
cout << minr << " " << minc << " " << maxr << " " << maxc << endl;
}
int colour(int ar, int ac, int br, int bc) {
ar = max(ar, minr);
ac = max(ac, minc);
br = min(br, maxr);
bc = min(bc, maxc);
return 1 + (ar == minr && ac == minc && br == maxr && bc == maxc)
- river_cells.Query(2 * ar, 2 * br, 2 * ac, 2 * bc);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
