#include <bits/stdc++.h>
#include "rainbow.h"
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
struct BIT2D {
int n;
vector <vector <int>> val;
vector <vector <int>> bit;
BIT2D(int _n = 0) {
n = _n;
bit.resize(n + 5);
val.resize(n + 5);
}
void fakeupdate(int x, int y) {
for (; x <= n; x += x & -x)
val[x].push_back(y);
}
void build() {
for (int i = 1; i <= n; i++) {
sort(ALL(val[i]));
val[i].resize(unique(ALL(val[i])) - val[i].begin());
bit[i].resize(val[i].size() + 1);
}
}
void update(int x, int y) {
for (; x <= n; x += x & -x) {
int i = lower_bound(ALL(val[x]), y) - val[x].begin() + 1;
for (; i < (int) bit[x].size(); i += i & -i)
bit[x][i]++;
}
}
int getsum(int x, int y) {
int res = 0;
for (; x; x -= x & -x) {
int i = upper_bound(ALL(val[x]), y) - val[x].begin();
for (; i; i -= i & -i)
res += bit[x][i];
}
return res;
}
int getsum(int x, int y, int u, int v) {
if (x > u || y > v)
return 0;
return (getsum(u, v) + getsum(x - 1, y - 1))
- (getsum(u, y - 1) + getsum(x - 1, v));
}
};
int fix(char c) {
if (c == 'W')
return 3;
if (c == 'N')
return 2;
if (c == 'E')
return 1;
return 0;
}
BIT2D row, col, cell, face;
set <pair <int, int>> s, r, c, f;
int maxx, maxy, minx, miny;
void add(int sc, int sr) {
s.insert({sr, sc});
s.insert({sr + 1, sc});
s.insert({sr, sc + 1});
s.insert({sr + 1, sc + 1});
f.insert({sr + 1, sc + 1});
r.insert({sr, sc + 1});
r.insert({sr + 1, sc + 1});
c.insert({sr + 1, sc});
c.insert({sr + 1, sc + 1});
maxi(maxx, sr);
maxi(maxy, sc);
mini(minx, sr);
mini(miny, sc);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
row = col = cell = face = BIT2D(R + 1);
minx = maxx = sr;
miny = maxy = sc;
add(sr, sc);
for (int i = 0; i < M; i++) {
int dir = fix(S[i]);
sr += dx[dir];
sc += dy[dir];
add(sr, sc);
}
for (auto [x, y] : s)
cell.fakeupdate(x, y);
for (auto [x, y] : r)
row.fakeupdate(x, y);
for (auto [x, y] : c)
col.fakeupdate(x, y);
for (auto [x, y] : f)
face.fakeupdate(x, y);
cell.build();
row.build();
col.build();
face.build();
for (auto [x, y] : s)
cell.update(x, y);
for (auto [x, y] : r)
row.update(x, y);
for (auto [x, y] : c)
col.update(x, y);
for (auto [x, y] : f)
face.update(x, y);
}
int colour(int x, int y, int u, int v) {
int C = 1 + (x < minx && maxx < u && y < miny && maxy < v);
v++;
u++;
int R = face.getsum(x + 1, y + 1, u, v);
int V = cell.getsum(x + 1, y + 1, u - 1, v - 1);
int E = row.getsum(x + 1, y, u - 1, v)
+ col.getsum(x, y + 1, u, v - 1);
// cerr << V << " " << E << " " << C << " " << R << "\n";
int F = 1 + (C + E - V);
return F - R - 1;
}
//#include "grader.cpp"
Compilation message
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:128:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
128 | for (auto [x, y] : s)
| ^
rainbow.cpp:131:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
131 | for (auto [x, y] : r)
| ^
rainbow.cpp:134:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
134 | for (auto [x, y] : c)
| ^
rainbow.cpp:137:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
137 | for (auto [x, y] : f)
| ^
rainbow.cpp:146:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
146 | for (auto [x, y] : s)
| ^
rainbow.cpp:149:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
149 | for (auto [x, y] : r)
| ^
rainbow.cpp:152:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
152 | for (auto [x, y] : c)
| ^
rainbow.cpp:155:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
155 | for (auto [x, y] : f)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 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 |
Correct |
511 ms |
121452 KB |
Output is correct |
| 3 |
Correct |
970 ms |
137920 KB |
Output is correct |
| 4 |
Correct |
830 ms |
128452 KB |
Output is correct |
| 5 |
Incorrect |
698 ms |
114764 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
