oj.uz

Submission #787753

# Submission time Handle Problem Language Result Execution time Memory
787753 2023-07-19T12:10:11 Z WLZ Sandcastle 2 (JOI22_ho_t5) C++17
15 / 100
 5000 ms 230416 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int INF = 0x3f3f3f3f;
 
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, w;
  cin >> h >> w;
  vector< vector<int> > grid(h + 2, vector<int>(w + 2));
  map<int, int> cmp_mp;
  for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) cin >> grid[i][j], cmp_mp[grid[i][j]] = -1;
  int cnt = 1;
  for (auto &p : cmp_mp) p.second = cnt++;
  for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) grid[i][j] = cmp_mp[grid[i][j]];
  if (h < w) {
    vector< vector<int> > grid2(w + 2, vector<int>(h + 2));
    for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) grid2[j][i] = grid[i][j];
    swap(grid2, grid); swap(h, w);
  }
  vector< vector< vector<int> > > in_deg(81, vector< vector<int> >(h + 2, vector<int>(w + 2, 0)));
  vector< vector<int> > used(h + 2, vector<int>(w + 2, 0));
  for (int type = 0; type < 81; type++) {
    vector<int> t(4);
    for (int i = 0, tmp = type; i < 4; i++) t[i] = tmp % 3, tmp /= 3;
    for (int r = 1; r <= h; r++) {
      for (int c = 1; c <= w; c++) {
        vector< pair<int, int> > neighbors, extra;
        used[r][c] = 1;
        for (int k = 0; k < 4; k++) {
          for (int i = 1; i <= t[k]; i++) {
            int nr = r + i * dx[k], nc = c + i * dy[k];
            if (nr >= 1 && nr <= h && nc >= 1 && nc <= w) {
              if (i == 1) neighbors.emplace_back(nr, nc);
              used[nr][nc] = 1;
              extra.emplace_back(nr, nc);
            }
          }
        }
        for (int nr = max(1, r - 2); nr <= min(h, r + 2); nr++) {
          for (int nc = max(1, c - 2); nc <= min(w, c + 2); nc++) {
            if (used[r][nc] && used[nr][c]) {
              used[nr][nc] = 1;
              extra.emplace_back(nr, nc);
            }
          }
        }
        for (auto &p : neighbors) {
          int nr = p.first, nc = p.second;
          int mx = -INF, mx_r = -1, mx_c = -1;
          for (int k = 0; k < 4; k++) {
            int nnr = nr + dx[k], nnc = nc + dy[k];
            if (nnr >= 1 && nnr <= h && nnc >= 1 && nnc <= w && used[nnr][nnc] && grid[nnr][nnc] < grid[nr][nc] && grid[nnr][nnc] > mx) {
              mx = grid[nnr][nnc];
              mx_r = nnr, mx_c = nnc;
            } 
          }
          in_deg[type][r][c] += (mx_r == r && mx_c == c);
        }
        for (auto &p : extra) used[p.first][p.second] = 0;
        used[r][c] = 0;
        in_deg[type][r][c] = (1 ? in_deg[type][r][c] == 0 : 0);
      }
    }
  }
  for (int type = 0; type < 81; type++) {
    for (int r = 1; r <= h; r++) for (int c = 1; c <= w; c++) in_deg[type][r][c] += in_deg[type][r - 1][c] + in_deg[type][r][c - 1] - in_deg[type][r - 1][c - 1];
  }
 
  auto get_sum = [&](int type, int r1, int c1, int r2, int c2) {
    if (r2 < r1 || c2 < c1 || r1 < 1 || r2 > h || c1 < 1 || c2 > w) return 0;
    return in_deg[type][r2][c2] - in_deg[type][r1 - 1][c2] - in_deg[type][r2][c1 - 1] + in_deg[type][r1 - 1][c1 - 1];
  };
 
  auto brute_force = [&](int r1, int c1, int r2, int c2) {
    int r = r1, c = c1;
    for (int nr = r1; nr <= r2; nr++) for (int nc = c1; nc <= c2; nc++) if (grid[nr][nc] > grid[r][c]) r = nr, c = nc;
    int cnt = 0;
    while (true) {
      cnt++;
      int mx = -INF, nr = -1, nc = -1;
      for (int k = 0; k < 4; k++) {
        int nnr = r + dx[k], nnc = c + dy[k];
        if (nnr >= r1 && nnr <= r2 && nnc >= c1 && nnc <= c2 && grid[nnr][nnc] < grid[r][c] && grid[nnr][nnc] > mx) {
          mx = grid[nnr][nnc];
          nr = nnr, nc = nnc;
        } 
      }
      r = nr, c = nc;
      if (mx == -INF) break;
    }
    return cnt == (r2 - r1 + 1) * (c2 - c1 + 1);
  };

  auto in_range = [&](int r, int c, int r1, int c1, int r2, int c2) {
    return (r1 <= r && r <= r2) && (c1 <= c && c <= c2);
  };

  int ans = 0;
  for (int r1 = 1; r1 <= h; r1++) {
    for (int c1 = 1; c1 <= w; c1++) {
      for (int r2 = r1; r2 <= h; r2++) {
        for (int c2 = c1; c2 <= w; c2++) {
          set< tuple<int, int, int, int> > ranges = 
          {{r1, c1, r1, c1}, {r1, c1 + 1, r1, c1 + 1}, {r1, c1 + 2, r1, c2 - 2}, {r1, c2 - 1, r1, c2 - 1}, {r1, c2, r1, c2},
           {r1 + 1, c1, r1 + 1, c1}, {r1 + 1, c1 + 1, r1 + 1, c1 + 1}, {r1 + 1, c1 + 2, r1 + 1, c2 - 2}, {r1 + 1, c2 - 1, r1 + 1, c2 - 1}, {r1 + 1, c2, r1 + 1, c2},
           {r1 + 2, c1, r2 - 2, c1}, {r1 + 2, c1 + 1, r2 - 2, c1 + 1}, {r1 + 2, c1 + 2, r2 - 2, c2 - 2}, {r1 + 2, c2 - 1, r2 - 2, c2 - 1}, {r1 + 2, c2, r2 - 2, c2},
           {r2 - 1, c1, r2 - 1, c1}, {r2 - 1, c1 + 1, r2 - 1, c1 + 1}, {r2 - 1, c1 + 2, r2 - 1, c2 - 2}, {r2 - 1, c2 - 1, r2 - 1, c2 - 1}, {r2 - 1, c2, r2 - 1, c2},
           {r2, c1, r2, c1}, {r2, c1 + 1, r2, c1 + 1}, {r2, c1 + 2, r2, c2 - 2}, {r2, c2 - 1, r2, c2 - 1}, {r2, c2, r2, c2}};
          int tmp = 0;
          for (auto &p : ranges) {
            if (!in_range(get<0>(p), get<1>(p), r1, c1, r2, c2) || !in_range(get<2>(p), get<3>(p), r1, c1, r2, c2)) continue;
            int type = 0;
            for (int k = 0, s = 1; k < 4; k++, s *= 3) for (int i = 1; i <= 2; i++) if (in_range(get<0>(p) + i * dx[k], get<1>(p) + i * dy[k], r1, c1, r2, c2)) type += s;
            tmp += get_sum(type, get<0>(p), get<1>(p), get<2>(p), get<3>(p));
          }
          ans += (tmp == 1);
        }
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:79:8: warning: variable 'brute_force' set but not used [-Wunused-but-set-variable]
   79 |   auto brute_force = [&](int r1, int c1, int r2, int c2) {
      |        ^~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 5064 ms 230416 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 6 ms 420 KB Output is correct
6 Correct 6 ms 416 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 6 ms 420 KB Output is correct
6 Correct 6 ms 416 KB Output is correct
7 Correct 1204 ms 7220 KB Output is correct
8 Correct 1151 ms 7216 KB Output is correct
9 Correct 781 ms 1044 KB Output is correct
10 Correct 844 ms 1108 KB Output is correct
11 Correct 888 ms 3800 KB Output is correct
12 Correct 878 ms 3800 KB Output is correct
13 Correct 745 ms 980 KB Output is correct
14 Correct 391 ms 820 KB Output is correct
15 Correct 813 ms 1108 KB Output is correct
16 Correct 827 ms 1108 KB Output is correct

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 6 ms 420 KB Output is correct
6 Correct 6 ms 416 KB Output is correct
7 Correct 1204 ms 7220 KB Output is correct
8 Correct 1151 ms 7216 KB Output is correct
9 Correct 781 ms 1044 KB Output is correct
10 Correct 844 ms 1108 KB Output is correct
11 Correct 888 ms 3800 KB Output is correct
12 Correct 878 ms 3800 KB Output is correct
13 Correct 745 ms 980 KB Output is correct
14 Correct 391 ms 820 KB Output is correct
15 Correct 813 ms 1108 KB Output is correct
16 Correct 827 ms 1108 KB Output is correct
17 Execution timed out 5058 ms 32872 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 6 ms 420 KB Output is correct
6 Correct 6 ms 416 KB Output is correct
7 Correct 1204 ms 7220 KB Output is correct
8 Correct 1151 ms 7216 KB Output is correct
9 Correct 781 ms 1044 KB Output is correct
10 Correct 844 ms 1108 KB Output is correct
11 Correct 888 ms 3800 KB Output is correct
12 Correct 878 ms 3800 KB Output is correct
13 Correct 745 ms 980 KB Output is correct
14 Correct 391 ms 820 KB Output is correct
15 Correct 813 ms 1108 KB Output is correct
16 Correct 827 ms 1108 KB Output is correct
17 Execution timed out 5058 ms 32872 KB Time limit exceeded
18 Halted 0 ms 0 KB -