QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#391847 | #3039. Cleaning | zlxFTH | TL | 39ms | 212388kb | C++14 | 3.1kb | 2024-04-16 20:56:46 | 2024-04-16 20:56:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N = 2e3 + 5, M = N * N;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int n, m, q;
int ti, cnt, dfn[M], low[M], sd[M];
int in[M], mnR[M], mxR[M], mnC[M], mxC[M];
char s[N][N];
vector<int> G[M], E[M];
void tarjan(int u) {
static int tp, st[M];
low[u] = dfn[u] = ++ti;
st[++tp] = u;
for (auto v : G[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (!sd[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
++cnt, sd[u] = cnt;
while (st[tp] != u) sd[st[tp--]] = cnt;
--tp;
}
}
void preWork() {
static int h = 1, t = 0, q[M];
for (int i = 1; i <= cnt; ++i)
if (!in[i]) q[++t] = i;
while (h <= t) {
int u = q[h++];
for (auto v : E[u]) {
mnR[v] = min(mnR[v], mnR[u]);
mxR[v] = max(mxR[v], mxR[u]);
mnC[v] = min(mnC[v], mnC[u]);
mxC[v] = max(mxC[v], mxC[u]);
if (--in[v] == 0) q[++t] = v;
}
}
}
#define id(i, j) ((i - 1) * m + j)
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i) cin >> (s[i] + 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
for (int d = 0; d < 4; ++d) {
int x = i + dx[d], y = j + dy[d];
if (x <= 0 || y <= 0 || x > n || y > m) continue;
if (s[i][j] == 'U' && d == 1) continue;
if (s[i][j] == 'D' && d == 0) continue;
if (s[i][j] == 'L' && d == 3) continue;
if (s[i][j] == 'R' && d == 2) continue;
G[id(i, j)].push_back(id(x, y));
}
for (int i = 1; i <= n * m; ++i)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= cnt; ++i)
mnR[i] = mnC[i] = 1e9, mxR[i] = mxC[i] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
int u = id(i, j);
for (auto v : G[u]) if (sd[u] != sd[v]) {
E[sd[u]].push_back(sd[v]);
in[sd[v]] += 1;
}
u = sd[u];
mnR[u] = min(mnR[u], i);
mxR[u] = max(mxR[u], i);
mnC[u] = min(mnC[u], j);
mxC[u] = max(mxC[u], j);
}
preWork();
static int sum[N][N];
auto add = [&](int x1, int x2, int y1, int y2) {
sum[x1][y1] += 1;
sum[x1][y2 + 1] += -1;
sum[x2 + 1][y1] += -1;
sum[x2 + 1][y2 + 1] += 1;
};
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int u = sd[id(i, j)];
add(mnR[u], mxR[u], mnC[u], mxC[u]);
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
sum[i][j] += -sum[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1];
}
}
while (q--) {
int a, b, x, y;
cin >> a >> b >> x >> y;
int u = sd[id(x, y)];
if (a >= mnR[u] && a <= mxR[u] && b >= mnC[u] && b <= mxC[u]) {
int ans = 0;
for (int i = mnR[u]; i <= mxR[u]; ++i) {
for (int j = mnC[u]; j <= mxC[u]; ++j) {
int v = sd[id(i, j)];
if (a >= mnR[v] && a <= mxR[v] && b >= mnC[v] && b <= mxC[v]) ++ans;
}
}
cout << ans << "\n";
} else cout << 0 << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 39ms
memory: 212388kb
input:
1 1 1 L 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 24ms
memory: 210840kb
input:
5 5 5 DDDDD RDDDL RRDLL RUUUL UUUUU 1 1 5 5 2 2 5 5 3 3 5 5 4 4 5 5 5 5 5 5
output:
0 14 20 14 5
result:
ok 5 number(s): "0 14 20 14 5"
Test #3:
score: 0
Accepted
time: 31ms
memory: 211924kb
input:
10 10 15 DDDDDDDDLU LRDLRRDLLU DDDLRRDLLD RRLLDUULLD RRLLURLRLD RRLLRRLDLU RRLLURLULU UULLURLULU DRULUUUULD RRRLDRLRLD 7 4 2 5 4 7 6 8 6 6 5 6 5 6 9 6 9 10 5 5 2 5 4 3 7 9 4 4 10 9 1 5 9 9 8 9 1 4 7 8 10 2 5 10 7 9 1 3 7 6 7 7 5 6 10 2 2 6 4 2
output:
41 41 41 41 0 0 0 0 20 0 88 0 41 0 0
result:
ok 15 numbers
Test #4:
score: -100
Time Limit Exceeded
input:
1000 1000 300000 RLLLURUDLURULUURLUDDLDDDRDDRUUDLLURRDDLLDRDLLRRRULUULLRRLRURRLLUUUUDUDDLUURDULDUDRRRUDLULRLDRDDUDULUUURLDUDDDUULLURUDRLRDLRULDUDUDDDLDUULRUUDLRLDURURLDDLLRRUURLULLRULLDURUDDDRUUUURUULRRRLLDLLUURUULDDLDRDLLDURLRDURLRLLDLUDLRULDUUDLDLULLULDDLUDLLLRURRRUUDLRLDLDLRDULRUDDURDRRLDRLRULDUL...
output:
0 0 0 0 0 0 245868 0 0 0 0 0 0 0 0 0 0 0 0 98541 0 0 0 89575 0 361225 0 262684 0 0 0 0 0 0 0 0 0 0 0 0 311462 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 361225 0 0 0 0 0 0 0 0 0 62676 0 0 136413 0 0 0 0 246844 0 178165 0 62676 361225 136413 0 0 361225 0 361225 0 0 0 199089 0 0 0 311462 0 0 262684 0 199...