oj.uz

Submission #1045737

# Submission time Handle Problem Language Result Execution time Memory
1045737 2024-08-06T07:18:21 Z NeroZein Strah (COCI18_strah) C++17
110 / 110
 79 ms 23756 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 2003;

char c[N][N];
int down[N][N];

int sum(int l, int r) {
  return r * (r + 1) / 2 - l * (l - 1) / 2; 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> c[i][j]; 
    }
  }
  for (int i = n; i >= 1; --i) {
    for (int j = 1; j <= m; ++j) {
      if (c[i][j] == '#') {
        down[i][j] = i;
      } else {
        down[i][j] = (i == n ? n + 1 : down[i + 1][j]); 
      }
    }
  }
  long long ans = 0; 
  for (int i = 1; i <= n; ++i) {
    long long sumv = 0; 
    long long in_stack = 0; 
    vector<array<int, 3>> stk; 
    for (int j = m; j >= 1; --j) {
      int nr = j; 
      while (!stk.empty()) {
        auto [l, r, v] = stk.back();
        if (v <= (down[i][j] - i)) {
          break;
        } else {
          sumv -= (long long) (r - l + 1) * v * (v + 1) / 2;
          in_stack -= (long long) sum(l, r) * v * (v + 1) / 2;
          nr = r; 
          stk.pop_back(); 
        }
      }
      int v = (down[i][j] - i); 
      sumv += (long long) (nr - j + 1) * v * (v + 1) / 2; 
      in_stack += (long long) sum(j, nr) * v * (v + 1) / 2; 
      stk.push_back({j, nr, v});
      long long res = in_stack;
      res -= (long long) (j - 1) * sumv;
      ans += res; 
    }
  }
  cout << ans << '\n'; 
  return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2516 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6740 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13144 KB Output is correct
2 Correct 46 ms 19404 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 16476 KB Output is correct
2 Correct 79 ms 23368 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13660 KB Output is correct
2 Correct 51 ms 21704 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19804 KB Output is correct
2 Correct 56 ms 22704 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 23132 KB Output is correct
2 Correct 79 ms 23756 KB Output is correct