#ifndef LOCAL
#include "rainbow.h"
#endif
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;
const int N = 1e5 + 10;
const int dx[] = {- 1, 0, 0, 1};
const int dy[] = {0, - 1, 1, 0};
struct SegTree {
struct Node {
int prf[2] = {0, 0}, suf[2] = {0, 0};
int up = 0, down = 0, s = 0;
Node() {};
Node operator + (const Node& other) const {
Node res;
for(int i = 0; i < 2; ++ i) {
res.prf[i] = this -> prf[i];
res.suf[i] = other.suf[i];
}
res.up = this -> up + other.up;
res.down = this -> down + other.down;
res.s = this -> s + other.s;
int have[2] = {(this -> suf[0] & other.prf[0]), (this -> suf[1] & other.prf[1])};
res.up -= have[0];
res.down -= have[1];
res.s -= have[0] | have[1];
return res;
}
};
int n_node = 0;
vector<Node> tree = {};
void resize(int _n) { n_node = _n; tree.resize((n_node << 2) + 10); };
SegTree() {};
SegTree(int _n) { this -> resize(_n); };
void update(int node, int l, int r, int idx, int val[2]) {
if(l == r) {
for(int i = 0; i < 2; ++ i) {
tree[node].prf[i] = tree[node].suf[i] = val[i];
}
tree[node].up += val[0];
tree[node].down += val[1];
tree[node].s += val[0] | val[1];
return;
}
int mid = (l + r) >> 1;
if(idx <= mid) update(node << 1, l, mid, idx, val);
else update(node << 1 | 1, mid + 1, r, idx, val);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
void Update(int idx, int val[2]) {
return update(1, 1, n_node, idx, val);
}
Node query(int node, int l, int r, int L, int R) {
if(l > r || L > R || l > R || L > r) return Node();
if(L <= l && r <= R) return tree[node];
int mid = (l + r) >> 1;
if(R <= mid) return query(node << 1, l, mid, L, R);
else if(L > mid) return query(node << 1 | 1, mid + 1, r, L, R);
return query(node << 1, l, mid, L, R) + query(node << 1 | 1, mid + 1, r, L, R);
}
Node Query(int l, int r) {
return query(1, 1, n_node, l, r);
}
};
int n, m, q;
int len, x, y;
char s[N];
bool un_go[3][200010];
SegTree st;
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R; m = C; x = sr; y = sc; len = M;
for(int i = 0; i < len; ++ i) s[i] = S[i];
if(n == 2) {
un_go[x][y] = true;
for(int i = 0; i < len; ++ i) {
if(s[i] == 'N') -- x;
else if(s[i] == 'S') ++ x;
else if(s[i] == 'E') ++ y;
else -- y;
un_go[x][y] = true;
}
st.resize(m);
for(int i = 1; i <= m; ++ i) {
int val[2] = {un_go[1][i], un_go[2][i]};
st.Update(i, val);
}
}
}
int colour(int ar, int ac, int br, int bc) {
if(n != 2) return 0;
int up = ar, le = ac, down = br, ri = bc;
const auto& res = st.Query(le, ri);
if(up == down) {
if(up == 1) return res.up;
else return res.down;
}
else return res.s;
}
/// Code by vuavisao
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
