#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], rip[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 {
int t[N * 4], lens[N];
int size = 0;
pair<int, int> segs[N];
bool full = false;
void build(int v, int L, int R) {
if (L == R) {
t[v] = lens[L];
}
else {
int m = (L + R) >> 1;
build(v * 2, L, m);
build(v * 2 + 1, m + 1, R);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
void init(int n) {
for (int i = 0, j = -1; i < n; i++) {
if (a[i]) {
if (i == n - 1 || a[i + 1] == 0) {
segs[size] = {j + 1, i};
lens[size] = i - j;
size++;
}
}
else {
j = i;
}
}
// for (int i = 0; i < size; i++) {
// cout << lens[i] << " ";
// }
// cout << "\n";
if (size > 0)
build(1, 0, size - 1);
full = (size == 1 && lens[0] == m + m);
}
int getFirstGreaterOrEqual(int x, int y, int v, int L, int R) {
if (R < x)
return -1;
if (t[v] < y)
return -1;
if (L == R)
return L;
int m = (L + R) >> 1,
ans = getFirstGreaterOrEqual(x, y, v * 2, L, m);
if (ans == -1)
ans = getFirstGreaterOrEqual(x, y, v * 2 + 1, m + 1, R);
return ans;
}
int getMax(int l, int r, int v, int L, int R) {
if (l > r)
return 0;
if (l == L && r == R)
return t[v];
int m = (L + R) >> 1;
return max(getMax(l, min(m, r), v * 2, L, m),
getMax(max(m + 1, l), r, v * 2 + 1, m + 1, R));
}
int getFirstAppropriate(int x, int y) {
int j = upper_bound(segs, segs + size, make_pair(x + 1, -1)) - segs;
if (j > 0 && segs[j - 1].second - x + 1 >= y)
return x + y - 1;
int k = getFirstGreaterOrEqual(j, y, 1, 0, size - 1);
if (k == -1)
return -1;
return segs[k].first + y - 1;
}
Node getSum(int l, int r) {
Node res = { 0, 0, 0, r - l + 1 };
int j = upper_bound(segs, segs + size, make_pair(l + 1, -1)) - segs,
k = upper_bound(segs, segs + size, make_pair(r + 1, -1)) - segs;
if (j > 0)
res.left = max(0, segs[j - 1].second - l + 1);
if (k > 0 && segs[k - 1].second >= r) {
res.right = segs[k - 1].second - r + 1;
k -= 2;
}
else {
k--;
}
res.inner = getMax(j, k, 1, 0, size - 1);
return res;
}
Node que(int l, int r) {
int cur_len = r - l + 1;
if (full)
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);
}
} 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 && !rip[p][q]) {
// cout << e.x << " " << e.y << " " << p << " " << q << "\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]].full) {
new_expected_time = e.t + rest;
rip[p][q] = 1;
}
else {
Node node = t[mask[p][q]].getSum((e.t + 1) % m, m + m - 1);
// cout << (e.t + 1) % m << " " << m + m - 1 << " " << node.left << " " << node.inner << " " << node.right << "\n";
if (node.left >= rest) {
new_expected_time = e.t + rest;
rip[p][q] = 1;
}
else {
int k = t[mask[p][q]].getFirstAppropriate((e.t + 1) % m, resistance[p][q]);
if (k != -1)
new_expected_time = k - (e.t + 1) % m + 1 + e.t;
}
}
if (new_expected_time != INF)
pq.push({ new_expected_time, p, q });
}
}
}
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;
rip[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;
}
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].init(n);
// int q;
// cin >> q;
// while (q--) {
// int x, y;
// cin >> x >> y;
// cout << t[0].getFirstAppropriate(x - 1, y) + 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].init(m + m);
}
pair<int, int> order[Z * Z];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> resistance[i][j];
order[i * c + j] = { i, j };
}
}
// handle(0, 0);
// cout << infected_count << "\n";
// return 0;
mt19937 rnd(time(0));
shuffle(order, order + r * c, rnd);
for (int x = 0; x < r * c; x++) {
int i = order[x].first,
j = order[x].second;
if (resistance[i][j] != 0) {
handle(i, j);
if (infected_count < mn) {
mn = infected_count;
ct = 0;
}
if (infected_count == mn)
ct++;
}
}
cout << mn << "\n" << ct;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
26360 KB |
Output is correct |
| 2 |
Runtime error |
62 ms |
51576 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
25720 KB |
Output is correct |
| 2 |
Correct |
30 ms |
26780 KB |
Output is correct |
| 3 |
Correct |
59 ms |
36512 KB |
Output is correct |
| 4 |
Correct |
30 ms |
26780 KB |
Output is correct |
| 5 |
Correct |
55 ms |
36508 KB |
Output is correct |
| 6 |
Execution timed out |
2065 ms |
36380 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
26360 KB |
Output is correct |
| 2 |
Runtime error |
62 ms |
51576 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
