oj.uz

Submission #1055577

# Submission time Handle Problem Language Result Execution time Memory
1055577 2024-08-12T22:32:40 Z MilosMilutinovic Sandcastle 2 (JOI22_ho_t5) C++14
10 / 100
 5000 ms 64528 KB 
#include <bits/stdc++.h>
 
using namespace std;

const int inf = (int) 1.001e9;
 
const int di[] = {1, -1, 0, 0};
const int dj[] = {0, 0, 1, -1};
 
const int L = 17;
 
vector<vector<int>> st[L][L];
 
vector<vector<long long>> f[1 << 4];
 
int logs[50005];
 
int Query(int x1, int y1, int x2, int y2) {
  int kx = logs[x2 - x1 + 1];
  int ky = logs[y2 - y1 + 1];
  return max({st[kx][ky][x1][y1], st[kx][ky][x2 - (1 << kx) + 1][y1], st[kx][ky][x1][y2 - (1 << ky) + 1],
            st[kx][ky][x2 - (1 << kx) + 1][y2 - (1 << ky) + 1]});
}
 
long long GetSum(int x1, int y1, int x2, int y2, int mask) {
  if (x1 > x2 || y1 > y2) {
    return 0LL;
  }
  long long res = f[mask][x2][y2];
  if (x1 > 0) {
    res -= f[mask][x1 - 1][y2];
  }
  if (y1 > 0) {
    res -= f[mask][x2][y1 - 1];
  }
  if (x1 > 0 && y1 > 0) {
    res += f[mask][x1 - 1][y1 - 1];
  }
  return res;
}
 
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];
    }
  }
  if (n > m) {
    vector<vector<int>> b(m, vector<int>(n));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        b[j][i] = a[i][j];
      }
    }
    a = b;
    swap(n, m);
  }
  for (int i = 2; i <= max(n, m); i++) {
    logs[i] = logs[i >> 1] + 1;
  }
  for (int i = 0; i < L; i++) {
    for (int j = 0; j < L; j++) {
      st[i][j] = vector<vector<int>>(n, vector<int>(m));
    }
  }
  for (int mask = 0; mask < (1 << 4); mask++) {
    f[mask] = vector<vector<long long>>(n, vector<long long>(m));
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      st[0][0][i][j] = 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[k][0][i][j] = max(st[k - 1][0][i][j], st[k - 1][0][i + (1 << (k - 1))][j]);
      }
    }
  }
  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[t][k][i][j] = max(st[t][k - 1][i][j], st[t][k - 1][i][j + (1 << (k - 1))]);
        }
      }
    }
  }
  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[mask][i][j] += f[mask][i - 1][j];
        }
        if (j > 0) {
          f[mask][i][j] += f[mask][i][j - 1];
        }
        if (i > 0 && j > 0) {
          f[mask][i][j] -= f[mask][i - 1][j - 1];
        }
        f[mask][i][j] -= a[i][j];
        int mx = 0;
        int cnt = 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]);
            }
            if (0 <= ni && ni < n && 0 <= nj && nj < m && a[ni][nj] > a[i][j]) {
              cnt += 1;
            }
          }
        }
        if (cnt == 0) {
          mx += n * m + a[i][j];
        }
        f[mask][i][j] += mx;
      }
    }
  }
  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;
          }
          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 == n * m) {
            res += 1;
          }
        }
      }
    }
  }
  cout << res << '\n';
  return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:139:15: warning: unused variable 'mx' [-Wunused-variable]
  139 |           int mx = Query(x1, y1, x2, y2);
      |               ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 5091 ms 64528 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 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 9 ms 2396 KB Output is correct
8 Correct 8 ms 2444 KB Output is correct
9 Correct 10 ms 2684 KB Output is correct
10 Correct 10 ms 2668 KB Output is correct
11 Correct 8 ms 2396 KB Output is correct
12 Correct 8 ms 2428 KB Output is correct
13 Correct 10 ms 2648 KB Output is correct
14 Correct 5 ms 2160 KB Output is correct
15 Correct 11 ms 2668 KB Output is correct
16 Incorrect 11 ms 2672 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 9 ms 2396 KB Output is correct
8 Correct 8 ms 2444 KB Output is correct
9 Correct 10 ms 2684 KB Output is correct
10 Correct 10 ms 2668 KB Output is correct
11 Correct 8 ms 2396 KB Output is correct
12 Correct 8 ms 2428 KB Output is correct
13 Correct 10 ms 2648 KB Output is correct
14 Correct 5 ms 2160 KB Output is correct
15 Correct 11 ms 2668 KB Output is correct
16 Incorrect 11 ms 2672 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 9 ms 2396 KB Output is correct
8 Correct 8 ms 2444 KB Output is correct
9 Correct 10 ms 2684 KB Output is correct
10 Correct 10 ms 2668 KB Output is correct
11 Correct 8 ms 2396 KB Output is correct
12 Correct 8 ms 2428 KB Output is correct
13 Correct 10 ms 2648 KB Output is correct
14 Correct 5 ms 2160 KB Output is correct
15 Correct 11 ms 2668 KB Output is correct
16 Incorrect 11 ms 2672 KB Output isn't correct
17 Halted 0 ms 0 KB -