#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
int convert(int x) {
return x*2+1;
}
struct seg {
struct node {
int val=0, l=-1, r=-1;
};
vector<node> tree;
seg() {
tree.assign(2, node());
}
int update(int v, int rl, int rr, int pos, int x) {
int newV = tree.size();
tree.push_back(tree[v]);
if (rl == rr) {
assert(pos == rl);
tree[newV].val += x;
return newV;
}
if (tree[newV].l == -1) {tree[newV].l = tree.size(); tree.push_back(node());}
if (tree[newV].r == -1) {tree[newV].r = tree.size(); tree.push_back(node());}
int rm = (rl + rr)/2;
if (pos <= rm) {
tree[newV].l = update(tree[newV].l, rl, rm, pos, x);
}
else {
tree[newV].r = update(tree[newV].r, rm+1, rr, pos, x);
}
tree[newV].val = tree[tree[newV].l].val + tree[tree[newV].r].val;
return newV;
}
int query(int v, int rl, int rr, int ql, int qr) {
if (ql > qr) return 0;
if (ql == rl && qr == rr) {
return tree[v].val;
}
int rm = (rl + rr)/2;
if (tree[v].l == -1) {tree[v].l = tree.size(); tree.push_back(node());}
if (tree[v].r == -1) {tree[v].r = tree.size(); tree.push_back(node());}
return query(tree[v].r, rm+1, rr, max(ql, rm+1), qr) + query(tree[v].l, rl, rm, ql, min(qr, rm));
}
};
seg squares = seg();
seg edgesFrst = seg();
seg edgesScnd = seg();
seg nodes = seg();
vector<int> queryTimeNodes;
vector<int> queryTimeSquares;
vector<int> queryTimeEdgesFrst;
vector<int> queryTimeEdgesScnd;
vector<pair<int, int>> eightConnected = {
{1, 1},
{-1, -1},
{1, -1},
{-1, 1},
{0, 1},
{0, -1},
{1, 0},
{-1, 0},
};
int R, C;
void init(signed r, signed c, signed sr, signed sc, signed M, char *S) {
R = r+4; C = c+4;
R = R*2 + 1;
C = C*2 + 1;
map<char, pair<int, int>> dir;
dir['N'] = {-2, 0};
dir['S'] = {2, 0};
dir['W'] = {0, -2};
dir['E'] = {0, 2};
pair<int, int> pos = {convert(sr+1), convert(sc+1)}; // We can use 2-indexed because we added 1 margin!
set<pair<int, int>> rivers;
rivers.insert(pos);
for (auto j: eightConnected) {
rivers.insert({pos.first + j.first, pos.second + j.second});
}
for (int i = 0; i<M; i++) {
pos.first += dir[S[i]].first;
pos.second += dir[S[i]].second;
rivers.insert(pos);
for (auto j: eightConnected) {
rivers.insert({pos.first + j.first, pos.second + j.second});
}
}
set<pair<int, int>> eFrst, eScnd, sqrs;
for (auto i: rivers) {
bool scnd = rivers.count({i.first, i.second+1});
bool frst = rivers.count({i.first+1, i.second});
bool frstscnd = rivers.count({i.first+1, i.second+1});
if (scnd) eScnd.insert(i);
if (frst) eFrst.insert(i);
if (scnd&&frst&&frstscnd) sqrs.insert(i);
}
queryTimeNodes.clear();
{
int ROW = 0;
int root = 1;
for (auto i: rivers) {
while (i.first > ROW) {
ROW++;
queryTimeNodes.push_back(root);
}
root = nodes.update(root, 0, C-1, i.second, 1);
}
while ((int)queryTimeNodes.size() < R) queryTimeNodes.push_back(root);
}
queryTimeSquares.clear();
{
int ROW = 0;
int root = 1;
for (auto i: sqrs) {
while (i.first > ROW) {
ROW++;
queryTimeSquares.push_back(root);
}
root = squares.update(root, 0, C-1, i.second, 1);
}
while ((int)queryTimeSquares.size() < R) queryTimeSquares.push_back(root);
}
queryTimeEdgesFrst.clear();
{
int ROW = 0;
int root = 1;
for (auto i: eFrst) {
while (i.first > ROW) {
ROW++;
queryTimeEdgesFrst.push_back(root);
}
root = edgesFrst.update(root, 0, C-1, i.second, 1);
}
while ((int)queryTimeEdgesFrst.size() < R) queryTimeEdgesFrst.push_back(root);
}
queryTimeEdgesScnd.clear();
{
int ROW = 0;
int root = 1;
for (auto i: eScnd) {
while (i.first > ROW) {
ROW++;
queryTimeEdgesScnd.push_back(root);
}
root = edgesScnd.update(root, 0, C-1, i.second, 1);
}
while ((int)queryTimeEdgesScnd.size() < R) queryTimeEdgesScnd.push_back(root);
}
}
signed colour(signed ar, signed ac, signed br, signed bc) {
ar++; ac++; br++; bc++; // We can use 2-indexed because we added 1 margin!
ar = convert(ar);
ac = convert(ac);
br = convert(br);
bc = convert(bc);
int countNodes=0, countEdges=0, countSquares=0;
bool connected=0;
countNodes += nodes.query(queryTimeNodes[br], 0, C-1, ac, bc);
countNodes -= nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, bc);
countEdges += edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, ac, bc);
countEdges -= edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, ac, bc);
countEdges += edgesScnd.query(queryTimeEdgesScnd[br], 0, C-1, ac, bc-1);
countEdges -= edgesScnd.query(queryTimeEdgesScnd[ar-1], 0, C-1, ac, bc-1);
countSquares += squares.query(queryTimeSquares[br-1], 0, C-1, ac, bc-1);
countSquares -= squares.query(queryTimeSquares[ar-1], 0, C-1, ac, bc-1);
if (countNodes == 0) connected = 1;
connected=connected||nodes.query(queryTimeNodes[ar], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, bc);
connected=connected||nodes.query(queryTimeNodes[br], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[br-1], 0, C-1, ac, bc);
connected=connected||nodes.query(queryTimeNodes[br], 0, C-1, ac, ac)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, ac);
connected=connected||nodes.query(queryTimeNodes[br], 0, C-1, bc, bc)-nodes.query(queryTimeNodes[ar-1], 0, C-1, bc, bc);
// cerr << "edges:" << countEdges << " " << "nodes:" << countNodes << " " << "squares:" << countSquares << " " << "connected:" << connected << "\n";
if (!connected) {
return countEdges-countNodes+2-countSquares;
}
int lenR = br-ar+1, lenC = bc-ac+1;
countNodes+=2*(lenR+lenC)+4;
// countNodes-=nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[ar-2], 0, C-1, ac, bc);
// countNodes-=nodes.query(queryTimeNodes[br+1], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[br], 0, C-1, ac, bc);
// countNodes-=nodes.query(queryTimeNodes[br], 0, C-1, ac-1, ac-1)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac-1, ac-1);
// countNodes-=nodes.query(queryTimeNodes[br], 0, C-1, bc+1, bc+1)-nodes.query(queryTimeNodes[ar-1], 0, C-1, bc+1, bc+1);
countEdges+=nodes.query(queryTimeNodes[ar], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, bc);
countEdges+=nodes.query(queryTimeNodes[br], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[br-1], 0, C-1, ac, bc);
countEdges+=nodes.query(queryTimeNodes[br], 0, C-1, ac, ac)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, ac);
countEdges+=nodes.query(queryTimeNodes[br], 0, C-1, bc, bc)-nodes.query(queryTimeNodes[ar-1], 0, C-1, bc, bc);
countEdges+=2*(lenR-1+lenC-1)+8;
// countEdges-=edgesScnd.query(queryTimeEdgesScnd[ar-1], 0, C-1, ac, bc-1)-edgesScnd.query(queryTimeEdgesScnd[ar-2], 0, C-1, ac, bc-1);
// countEdges-=edgesScnd.query(queryTimeEdgesScnd[br+1], 0, C-1, ac, bc-1)-edgesScnd.query(queryTimeEdgesScnd[br], 0, C-1, ac, bc-1);
// countEdges-=edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, ac-1, ac-1)-edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, ac-1, ac-1);
// countEdges-=edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, bc+1, bc+1)-edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, bc+1, bc+1);
countSquares+=edgesScnd.query(queryTimeEdgesScnd[ar], 0, C-1, ac, bc-1)-edgesScnd.query(queryTimeEdgesScnd[ar-1], 0, C-1, ac, bc-1);
countSquares+=edgesScnd.query(queryTimeEdgesScnd[br], 0, C-1, ac, bc-1)-edgesScnd.query(queryTimeEdgesScnd[br-1], 0, C-1, ac, bc-1);
countSquares+=edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, ac, ac)-edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, ac, ac);
countSquares+=edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, bc, bc)-edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, bc, bc);
if (nodes.query(queryTimeNodes[ar], 0, C-1, ac, ac) - nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, ac)) countSquares++;
if (nodes.query(queryTimeNodes[br], 0, C-1, ac, ac) - nodes.query(queryTimeNodes[br-1], 0, C-1, ac, ac)) countSquares++;
if (nodes.query(queryTimeNodes[ar], 0, C-1, bc, bc) - nodes.query(queryTimeNodes[ar-1], 0, C-1, bc, bc)) countSquares++;
if (nodes.query(queryTimeNodes[br], 0, C-1, bc, bc) - nodes.query(queryTimeNodes[br-1], 0, C-1, bc, bc)) countSquares++;
// cerr << "edges:" << countEdges << " " << "nodes:" << countNodes << " " << "squares:" << countSquares << " " << "connected:" << connected << "\n";
return countEdges-countNodes-countSquares+1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1304 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
859 ms |
263940 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1304 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1304 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
