QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#391847#3039. CleaningzlxFTHTL 39ms212388kbC++143.1kb2024-04-16 20:56:462024-04-16 20:56:47

Judging History

你现在查看的是最新测评结果

  • [2024-04-16 20:56:47]
  • 评测
  • 测评结果:TL
  • 用时:39ms
  • 内存:212388kb
  • [2024-04-16 20:56:46]
  • 提交

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...

result: