#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
struct Node {
int left, right, inner, len;
};
const int N = 2e5 + 5, Z = 51, INF = 2e9;
string s;
char dir[5] = "WESN";
int m, r, c;
int a[N], resistance[Z][Z], mask[Z][Z], last_ch[Z][Z],
dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};
Node tail[Z][Z];
bool infected[Z][Z];
Node operator + (Node a, Node b) {
Node c;
c.len = a.len + b.len;
c.inner = max(a.inner, b.inner);
c.inner = max(c.inner, a.right + b.left);
c.left = a.left + (a.inner == a.len ? b.left : 0);
c.right = b.right + (b.inner == b.len ? a.right : 0);
return c;
}
struct SegTree {
Node t[N * 4];
void build(int v, int L, int R) {
if (L == R) {
t[v] = {a[L], a[L], a[L], 1};
}
else {
int m = (L + R) >> 1;
build(v * 2, L, m);
build(v * 2 + 1, m + 1, R);
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
Node getFirstGreaterOrEqual(int x, int y, int v = 1, int L = 0, int R = m + m - 1) {
if (R < x)
return { 0, 0, 0, 0 };
if (L == R)
return t[v].inner >= y ? Node{ L, -1 } : t[v];
if (L >= x && t[v].inner < y)
return t[v];
int m = (L + R) >> 1;
if (x > m)
return getFirstGreaterOrEqual(x, y, v * 2 + 1, m + 1, R);
Node ln = getFirstGreaterOrEqual(x, y, v * 2, L, m);
if (ln.right == -1)
return ln;
if (ln.right + t[v * 2 + 1].left >= y)
return { m + y - ln.right, -1 };
if (t[v * 2 + 1].inner >= y)
return getFirstGreaterOrEqual(x, y, v * 2 + 1, m + 1, R);
return ln + t[v * 2 + 1];
}
Node getSum(int l, int r, int v = 1, int L = 0, int R = m + m - 1) {
if (l > r)
return { 0, 0, 0, 0 };
if (l == L && r == R)
return t[v];
int m = (L + R) >> 1;
return getSum(l, min(m, r), v * 2, L, m) +
getSum(max(m + 1, l), r, v * 2 + 1, m + 1, R);
}
Node que(int l, int r) {
int cur_len = r - l + 1;
if (t[1].inner == t[1].len)
return { cur_len, cur_len, cur_len, cur_len };
if (cur_len >= m)
l = r - m + 2;
if (l > r)
return { 0, 0, 0, 0 };
r %= m;
l %= m;
if (l > r)
r += m;
return getSum(l, r);
}
// void print(int v, int L, int R) {
// cout << L << " " << R << "\n" << t[v].left << " " << t[v].inner << " " << t[v].right << " " << t[v].len << "\n\n";
// if (L != R) {
// int m = (L + R) >> 1;
// print(v * 2, L, m);
// print(v * 2 + 1, m + 1, R);
// }
// }
} t[1 << 4];
struct Event {
int t, x, y;
bool operator < (const Event &oth) const {
return t > oth.t;
}
};
priority_queue<Event> pq;
int infected_count = 0;
void eventHappens(Event e) {
if (infected[e.x][e.y])
return;
infected[e.x][e.y] = 1;
infected_count++;
for (int i = 0; i < 4; i++) {
int p = e.x + dx[i],
q = e.y + dy[i];
if (p >= 0 && p < r && q >= 0 && q < c &&
!infected[p][q] && resistance[p][q] != 0) {
// cout << e.x << " " << e.y << " " << p << " " << q << " " << e.t << "\n";
mask[p][q] |= 1 << i;
tail[p][q] = tail[p][q] + t[mask[p][q]].que(last_ch[p][q] + 1, e.t);
last_ch[p][q] = e.t;
int new_expected_time = INF, rest = resistance[p][q] - tail[p][q].right;
if (t[mask[p][q]].t[1].inner == m + m) {
new_expected_time = e.t + rest;
}
else {
Node node = t[mask[p][q]].getSum((e.t + 1) % m, m + m - 1);
if (node.left >= rest) {
new_expected_time = e.t + rest;
}
else {
node = t[mask[p][q]].getFirstGreaterOrEqual((e.t + 1) % m, resistance[p][q]);
if (node.right == -1)
new_expected_time = node.left - (e.t + 1) % m + 1 + e.t;
}
}
if (new_expected_time != INF)
pq.push({ new_expected_time, p, q });
// cout << "......\n\n";
}
}
}
int mn = INF, ct = 0;
void handle(int i, int j) {
for (int x = 0; x < r; x++) {
for (int y = 0; y < c; y++) {
mask[x][y] = 0;
last_ch[x][y] = -1;
tail[x][y] = { 0, 0, 0, 0 };
infected[x][y] = 0;
}
}
infected_count = 0;
pq.push({ -1, i, j });
while (!pq.empty()) {
Event e = pq.top();
pq.pop();
eventHappens(e);
if (infected_count > mn)
break;
// cout << e.t << "\n";
// for (int x = 0; x < r; x++) {
// for (int y = 0; y < c; y++) {
// cout << infected[x][y];
// }
// cout << "\n";
// }
// cout << "\n";
}
pq = priority_queue<Event>();
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
// int n;
// cin >> n;
// for (int i = 0; i < n; i++)
// cin >> a[i];
// t[0].build(1, 0, n - 1);
// // t[0].print(1, 0, n - 1);
// int q;
// cin >> q;
// while (q--) {
// int x, y;
// cin >> x >> y;
// x--;
// Node ans = t[0].que(x, y, 1, 0, n - 1);
// if (ans.right == -1)
// cout << ans.left + 1 << "\n";
// else
// cout << -1 << "\n";
// }
// return 0;
cin >> m >> r >> c >> s;
for (char &c : s) {
c = find(dir, dir + 4, c) - dir;
}
s += s;
for (int i = 0; i < (1 << 4); i++) {
for (int j = 0; j < m + m; j++) {
a[j] = (i >> s[j]) & 1;
}
t[i].build(1, 0, m + m - 1);
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> resistance[i][j];
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (resistance[i][j] != 0) {
handle(i, j);
if (infected_count < mn) {
mn = infected_count;
ct = 0;
}
if (infected_count == mn)
ct++;
//cout << i + 1 << " " << j + 1 << " : " << infected_count << "\n";
}
}
}
cout << mn << "\n" << ct;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
66808 KB |
Output is correct |
| 2 |
Runtime error |
351 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
152 ms |
133108 KB |
Output is correct |
| 3 |
Correct |
156 ms |
133100 KB |
Output is correct |
| 4 |
Correct |
151 ms |
133036 KB |
Output is correct |
| 5 |
Correct |
156 ms |
132992 KB |
Output is correct |
| 6 |
Execution timed out |
2058 ms |
133008 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
66808 KB |
Output is correct |
| 2 |
Runtime error |
351 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
