/*
APIO 2017 Rainbow
- We can view a rectangle as a planar graph
- Put temporary rivers on the outside of the rectangle
- Each river segment is a node and adjacent rivers constitute an edge
- This problem then becomes finding the number of faces of a planar graph
- We can solve this with Euler's formula
- By Euler's formula, we have
F = E - V + 1 + C
where F is faces, E is edges, V is vertices, and C is the number of components
- Each corner of a square is a vertex and each side of a square is an edge if it has a river
*/
#include "rainbow.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
int rnd() { return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15)); }
struct TreapNode {
TreapNode *l, *r;
int pos, key, mn, mx;
int val, g;
TreapNode(int position, int value) {
l = r = nullptr;
mn = mx = pos = position;
key = rnd();
val = g = value;
}
void update() {
g = val;
if (l) g += l->g;
if (r) g += r->g;
mn = (l ? l->mn : pos);
mx = (r ? r->mx : pos);
}
};
struct Treap {
TreapNode *root;
Treap() {
root = nullptr;
srand(rnd());
}
void split(TreapNode *t, int pos, TreapNode *&l, TreapNode *&r) {
if (t == nullptr) {
l = r = nullptr;
return;
}
if (t->pos < pos) {
split(t->r, pos, l, r);
t->r = l;
l = t;
} else {
split(t->l, pos, l, r);
t->l = r;
r = t;
}
t->update();
}
TreapNode* merge(TreapNode *l, TreapNode *r) {
if (!l || !r) return l ? l : r;
if (l->key < r->key) {
l->r = merge(l->r, r);
l->update();
return l;
} else {
r->l = merge(l, r->l);
r->update();
return r;
}
}
bool find(int pos) {
TreapNode *t = root;
while (t) {
if (t->pos == pos) return true;
if (t->pos > pos) t = t->l;
else t = t->r;
}
return false;
}
void update(TreapNode *t, int pos, int val) {
if (t->pos == pos) {
t->val = val;
t->update();
return;
}
if (t->pos > pos) update(t->l, pos, val);
else update(t->r, pos, val);
t->update();
}
void insert(int pos, int val) {
if (find(pos)) update(root, pos, val);
else {
TreapNode *l, *r;
split(root, pos, l, r);
root = merge(merge(l, new TreapNode(pos, val)), r);
}
}
int query(TreapNode *t, int st, int en) {
if (t->mx < st || en < t->mn) return 0;
if (st <= t->mn && t->mx <= en) return t->g;
int ans = (st <= t->pos && t->pos <= en ? t->val : 0);
if (t->l) ans += query(t->l, st, en);
if (t->r) ans += query(t->r, st, en);
return ans;
}
int query(int st, int en) {
if (!root) return 0;
return query(root, st, en);
}
};
struct Segtree {
Segtree *l, *r;
Treap treap;
int lo, hi;
Segtree() { l = r = nullptr; }
Segtree(int st, int en) {
l = r = nullptr;
lo = st, hi = en;
}
void new_left() {
if (!l) l = new Segtree(lo, (lo + hi) / 2);
}
void new_right() {
if (!r) r = new Segtree((lo + hi) / 2 + 1, hi);
}
void fix(int pos) {
int val = 0;
if (l) val += l->treap.query(pos, pos);
if (r) val += r->treap.query(pos, pos);
treap.insert(pos, val);
}
void update(int x, int y, int val) {
if (hi < x || x < lo) return;
if (lo == hi) {
treap.insert(y, val);
return;
}
if (x <= (lo + hi) / 2) {
new_left();
l->update(x, y, val);
} else {
new_right();
r->update(x, y, val);
}
fix(y);
}
int query(int t, int b, int st, int en) {
if (hi < t || b < lo) return 0;
if (t <= lo && hi <= b) return treap.query(st, en);
int ans = 0;
if (l) ans += l->query(t, b, st, en);
if (r) ans += r->query(t, b, st, en);
return ans;
}
};
Segtree segtree;
Segtree vertices, edges, rivers;
set<pair<int, int>> v, e, r;
int mx_r = 0, mn_r = 200001, mx_c = 0, mn_c = 200001;
void add_river(int x, int y) {
v.insert({x, y}); v.insert({x + 1, y}); v.insert({x, y + 1}); v.insert({x + 1, y + 1});
e.insert({2 * x - 1, 2 * y}); e.insert({2 * x + 1, 2 * y});
e.insert({2 * x, 2 * y - 1}); e.insert({2 * x, 2 * y + 1});
r.insert({x, y});
}
void init(int R, int C, int sr, int sc, int M, char *S) {
srand(12341234);
vertices = Segtree(1, R + 1);
edges = Segtree(1, 2 * R + 1);
rivers = Segtree(1, R);
add_river(sr, sc);
FOR(i, 0, M) {
if (S[i] == 'N') sr--;
if (S[i] == 'E') sc++;
if (S[i] == 'S') sr++;
if (S[i] == 'W') sc--;
add_river(sr, sc);
mx_r = max(mx_r, sr);
mn_r = min(mn_r, sr);
mx_c = max(mx_c, sc);
mn_c = min(mn_c, sc);
}
for (pair<int, int> i : v) vertices.update(i.first, i.second, 1);
for (pair<int, int> i : e) edges.update(i.first, i.second, 1);
for (pair<int, int> i : r) rivers.update(i.first, i.second, 1);
}
int colour(int ar, int ac, int br, int bc) {
int E = edges.query(2 * ar, 2 * br, 2 * ac, 2 * bc);
int V = vertices.query(ar + 1, br, ac + 1, bc);
int R = rivers.query(ar, br, ac, bc);
int C = (ar >= mn_r || br <= mx_r || ac >= mn_c || bc <= mx_c ? 1 : 2);
return E - V + C - R;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
632 KB |
Output is correct |
| 2 |
Correct |
18 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
7 ms |
632 KB |
Output is correct |
| 4 |
Correct |
8 ms |
760 KB |
Output is correct |
| 5 |
Correct |
21 ms |
1400 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
632 KB |
Output is correct |
| 2 |
Correct |
18 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
7 ms |
632 KB |
Output is correct |
| 4 |
Correct |
8 ms |
760 KB |
Output is correct |
| 5 |
Correct |
21 ms |
1400 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
632 KB |
Output is correct |
| 2 |
Correct |
18 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
7 ms |
632 KB |
Output is correct |
| 4 |
Correct |
8 ms |
760 KB |
Output is correct |
| 5 |
Correct |
21 ms |
1400 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
