oj.uz

Submission #697160

# Submission time Handle Problem Language Result Execution time Memory
697160 2023-02-08T16:54:49 Z kusssso Bob (COCI14_bob) C++17
120 / 120
 121 ms 8988 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1005;

int n, m;
int a[N][N];
ll ans;

signed main() {
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cin >> n >> m;
      for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) cin >> a[i][j];
      }
      vector<int> h(m + 1, 0);
      for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) h[j] = (a[i][j] == a[i - 1][j] ? h[j] + 1 : 1);
            // for (int j = 1; j <= m; j++) cout << h[j] << ' ';
            // cout << '\n';
            // continue;
            vector<int> l(m + 1, 0);
            vector<int> r(m + 1, 0);
            deque<int> d;
            for (int j = 1; j <= m; j++) {
                  int t;
                  for (t = j; t <= m && a[i][t] == a[i][j]; t++) {
                        while (!d.empty() && h[t] <= h[d.back()]) d.pop_back();
                        l[t] = (d.empty() ? j : d.back() + 1);
                        d.push_back(t);
                  }
                  j = t - 1;
                  d.clear();
            }
            for (int j = m; j >= 1; j--) {
                  int t;
                  for (t = j; t >= 1 && a[i][t] == a[i][j]; t--) {
                        while (!d.empty() && h[t] < h[d.back()]) d.pop_back();
                        r[t] = (d.empty() ? j : d.back() - 1);
                        d.push_back(t);
                  }
                  j = t + 1;
                  d.clear();
            }
            for (int j = 1; j <= m; j++) {
                  ans += 1LL * (j - l[j] + 1) * (r[j] - j + 1) * h[j];
            }
      }
      cout << ans;
      return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2824 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3244 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3448 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3516 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 8988 KB Output is correct
2 Correct 61 ms 6212 KB Output is correct
3 Correct 60 ms 6212 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 8272 KB Output is correct
2 Correct 70 ms 6236 KB Output is correct
3 Correct 58 ms 6180 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 8448 KB Output is correct
2 Correct 58 ms 6156 KB Output is correct
3 Correct 59 ms 6204 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 8484 KB Output is correct
2 Correct 65 ms 6188 KB Output is correct
3 Correct 61 ms 6092 KB Output is correct