#include "rainbow.h"
#include <bits/stdc++.h>
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maxi(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
if (a > b) { a = b; return 1; } return 0;
}
const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;
const char ch[4] = {'S', 'N', 'W', 'E'};
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
bool smallG = 0;
int n, m;
vector<ii> rivers;
namespace SUB1 {
const int N = (int)1e3 + 7;
int a[N][N], b[N][N];
int get(int a[N][N], int x, int y, int u, int v) {
if (x > u or y > v) return 0;
return a[u][v] - a[u][y - 1] - a[x - 1][v] + a[x - 1][y - 1];
}
int s1[N][N], s2[N][N], s3[N][N];
void build() {
FOR(i, 1, n)
FOR(j, 1, m) a[i][j] = 0;
for(auto x : rivers)
a[x.fi][x.se] = 1;
// FOR(i, 1, n) FOR(j, 1, m) cerr << a[i][j] << " \n"[j == m];
FOR(i, 1, n) FOR(j, 1, m) {
b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + (a[i][j]);
}
FOR(i, 1, n) {
FOR(j, 2, m) s1[i][j]
= s1[i - 1][j] + s1[i][j - 1] - s1[i - 1][j - 1] + (a[i][j] and a[i][j - 1]);
}
FOR(i, 2, n) {
FOR(j, 1, m) s2[i][j]
= s2[i - 1][j] + s2[i][j - 1] - s2[i - 1][j - 1] + (a[i][j] and a[i - 1][j]);
}
FOR(i, 2, n) FOR(j, 2, m) {
s3[i][j] = s3[i - 1][j] + s3[i][j - 1] - s3[i - 1][j - 1]
+ (a[i][j] and a[i][j-1] and a[i-1][j] and a[i-1][j-1]);
}
}
int get(int x, int y, int u, int v) {
int w = y - v + 1, h = u - x + 1;
int V = get(b, x, y, u, v) + 2 * (w + h) + 4;
int E = get(s1, x, y + 1, u, v) + get(s2, x + 1, y, u, v);
// cerr << "E: " << E << nl;
E += get(b, x, y, x, v) + get(b, u, y, u, v);
E += get(b, x, y, u, y) + get(b, x, v, u, v);
E += 2 * (w + 1) + 2 * (h + 1);
int F = 2 + E - V;
// cerr << E << ' ' << V << ' ' << F << nl;
F -= get(s2, x + 1, y, u, y);
F -= get(s2, x + 1, v, u, v);
F -= get(s1, x, y + 1, x, v);
F -= get(s1, u, y + 1, u, v);
F -= (a[x][y]) + (a[x][v]) + (a[u][y]) + (a[u][v]);
F -= get(s3, x + 1, y + 1, u, v);
return F - 1;
}
};
void init(int R, int C, int sx, int sy, int M, char *S) {
n = R, m = C;
rivers.push_back(_mp(sx, sy));
for(int i = 0; i < M; ++i) {
FOR(d, 0, 3) if (ch[d] == S[i]) {
sx += dx[d],
sy += dy[d];
}
rivers.push_back(_mp(sx, sy));
}
unq(rivers);
if (n <= 1000 and m <= 1000) {
smallG = 1;
}
if (smallG) {
SUB1::build();
}
}
int colour(int ar, int ac, int br, int bc) {
if (smallG) {
return SUB1::get(ar, ac, br, bc);
}
return 0;
}
/* Let the river flows naturally */
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 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 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
35 ms |
4556 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
1708 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
