oj.uz

Submission #1055557

# Submission time Handle Problem Language Result Execution time Memory
1055557 2024-08-12T21:48:18 Z MilosMilutinovic Sandcastle 2 (JOI22_ho_t5) C++14
15 / 100
 5000 ms 176744 KB 
#include <bits/stdc++.h>

using namespace std;

const int di[] = {1, -1, 0, 0};
const int dj[] = {0, 0, 1, -1};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> a(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
  const int L = 17;
  vector<vector<vector<vector<int>>>> st(n, vector<vector<vector<int>>>(m, vector<vector<int>>(L, vector<int>(L))));
  vector<int> logs(max(n, m) + 1);
  for (int i = 2; i <= max(n, m); i++) {
    logs[i] = logs[i >> 1] + 1;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      st[i][j][0][0] = a[i][j];
    }
  }
  for (int k = 1; k < L; k++) {
    for (int i = 0; i + (1 << k) <= n; i++) {
      for (int j = 0; j < m; j++) {
        st[i][j][k][0] = max(st[i][j][k - 1][0], st[i + (1 << (k - 1))][j][k - 1][0]);
      }
    }
  }
  for (int k = 1; k < L; k++) {
    for (int t = 0; t < L; t++) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j + (1 << k) <= m; j++) {
          st[i][j][t][k] = max(st[i][j][t][k - 1], st[i][j + (1 << (k - 1))][t][k - 1]);
        }
      }
    }
  }
  auto Query = [&](int x1, int y1, int x2, int y2) {
    int res = 0;
    for (int i = x1; i <= x2; i++) {
      for (int j = y1; j <= y2; j++) {
        res = max(res, a[i][j]);
      }
    }
    return res; 
    int kx = logs[x2 - x1 + 1];
    int ky = logs[y2 - y1 + 1];
    return max({st[x1][y1][kx][ky], st[x2 - (1 << kx) + 1][y1][kx][ky], st[x1][y2 - (1 << ky) + 1][kx][ky],
              st[x2 - (1 << kx) + 1][y2 - (1 << ky) + 1][kx][ky]});
  };
  vector<vector<vector<long long>>> f(n, vector<vector<long long>>(m, vector<long long>(1 << 4)));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int mask = 0; mask < (1 << 4); mask++) {
        if (i > 0) {
          f[i][j][mask] += f[i - 1][j][mask];
        }
        if (j > 0) {
          f[i][j][mask] += f[i][j - 1][mask];
        }
        if (i > 0 && j > 0) {
          f[i][j][mask] -= f[i - 1][j - 1][mask];
        }
        f[i][j][mask] -= a[i][j];
        int mx = 0;
        for (int d = 0; d < 4; d++) {
          if (mask >> d & 1) {
            int ni = i + di[d];
            int nj = j + dj[d];
            if (0 <= ni && ni < n && 0 <= nj && nj < m && a[ni][nj] < a[i][j]) {
              mx = max(mx, a[ni][nj]);
            }
          }
        }
        f[i][j][mask] += mx;
      }
    }
  }
  auto GetSum = [&](int x1, int y1, int x2, int y2, int mask) {
    if (x1 > x2 || y1 > y2) {
      return 0LL;
    }
    long long res = f[x2][y2][mask];
    if (x1 > 0) {
      res -= f[x1 - 1][y2][mask];
    }
    if (y1 > 0) {
      res -= f[x2][y1 - 1][mask];
    }
    if (x1 > 0 && y1 > 0) {
      res += f[x1 - 1][y1 - 1][mask];
    }
    return res;
  };
  int res = 0;
  for (int x1 = 0; x1 < n; x1++) {
    for (int y1 = 0; y1 < m; y1++) {
      for (int x2 = x1; x2 < n; x2++) {
        for (int y2 = y1; y2 < m; y2++) {
          if (x1 == x2 && y1 == y2) {
            res += 1;
            continue;
          }
          auto Valid = [&](int x, int y) {
            return x1 <= x && x <= x2 && y1 <= y && y <= y2;
          };
          long long s = 0;
          int mx = Query(x1, y1, x2, y2);
          if (x1 == x2) {
            {
              s += GetSum(x1, y1, x1, y1, 1 << 2);
            }
            {
              s += GetSum(x1, y2, x1, y2, 1 << 3);
            }
            if (y1 + 1 < y2) {
              s += GetSum(x1, y1 + 1, x1, y2 - 1, (1 << 2) + (1 << 3));
            }
          } else if (y1 == y2) {
            {
              s += GetSum(x1, y1, x1, y1, 1 << 0);
            }
            {
              s += GetSum(x2, y1, x2, y1, 1 << 1);
            }
            if (x1 + 1 < x2) {
              s += GetSum(x1 + 1, y1, x2 - 1, y1, (1 << 0) + (1 << 1));
            }
          } else {
            {
              s += GetSum(x1, y1, x1, y1, (1 << 0) + (1 << 2));
            }
            {
              s += GetSum(x1, y2, x1, y2, (1 << 0) + (1 << 3));
            }
            {
              s += GetSum(x2, y1, x2, y1, (1 << 1) + (1 << 2));
            }
            {
              s += GetSum(x2, y2, x2, y2, (1 << 1) + (1 << 3));
            }
            if (x1 + 1 < x2) {
              s += GetSum(x1 + 1, y1, x2 - 1, y1, (1 << 0) + (1 << 1) + (1 << 2));
              s += GetSum(x1 + 1, y2, x2 - 1, y2, (1 << 0) + (1 << 1) + (1 << 3));
            }
            if (y1 + 1 < y2) {
              s += GetSum(x1, y1 + 1, x1, y2 - 1, (1 << 2) + (1 << 3) + (1 << 0));
              s += GetSum(x2, y1 + 1, x2, y2 - 1, (1 << 2) + (1 << 3) + (1 << 1));
            }
            if (x1 + 1 < x2 && y1 + 1 < y2) {
              s += GetSum(x1 + 1, y1 + 1, x2 - 1, y2 - 1, (1 << 0) + (1 << 1) + (1 << 2) + (1 << 3));
            }
          }
          if (s == -mx) {
            res += 1;
          }
        }
      }
    }
  }
  cout << res << '\n';
  return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:112:16: warning: variable 'Valid' set but not used [-Wunused-but-set-variable]
  112 |           auto Valid = [&](int x, int y) {
      |                ^~~~~

Subtask #1
0 / 9.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 391 ms 3420 KB Output is correct
8 Correct 406 ms 3516 KB Output is correct
9 Correct 68 ms 3164 KB Output is correct
10 Correct 73 ms 3164 KB Output is correct
11 Correct 166 ms 4188 KB Output is correct
12 Correct 174 ms 3420 KB Output is correct
13 Correct 63 ms 3164 KB Output is correct
14 Correct 26 ms 2396 KB Output is correct
15 Correct 71 ms 3160 KB Output is correct
16 Correct 73 ms 3160 KB Output is correct

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 391 ms 3420 KB Output is correct
8 Correct 406 ms 3516 KB Output is correct
9 Correct 68 ms 3164 KB Output is correct
10 Correct 73 ms 3164 KB Output is correct
11 Correct 166 ms 4188 KB Output is correct
12 Correct 174 ms 3420 KB Output is correct
13 Correct 63 ms 3164 KB Output is correct
14 Correct 26 ms 2396 KB Output is correct
15 Correct 71 ms 3160 KB Output is correct
16 Correct 73 ms 3160 KB Output is correct
17 Execution timed out 5032 ms 14680 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 391 ms 3420 KB Output is correct
8 Correct 406 ms 3516 KB Output is correct
9 Correct 68 ms 3164 KB Output is correct
10 Correct 73 ms 3164 KB Output is correct
11 Correct 166 ms 4188 KB Output is correct
12 Correct 174 ms 3420 KB Output is correct
13 Correct 63 ms 3164 KB Output is correct
14 Correct 26 ms 2396 KB Output is correct
15 Correct 71 ms 3160 KB Output is correct
16 Correct 73 ms 3160 KB Output is correct
17 Execution timed out 5032 ms 14680 KB Time limit exceeded
18 Halted 0 ms 0 KB -