oj.uz

Submission #1045730

# Submission time Handle Problem Language Result Execution time Memory
1045730 2024-08-06T07:15:47 Z NeroZein Strah (COCI18_strah) C++17
55 / 110
 7 ms 1372 KB 
#include "bits/stdc++.h"
using namespace std;

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

const int N = 302;

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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 816 KB Output is correct

Subtask #5
11.0 / 11.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1112 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -