oj.uz

Submission #1013815

# Submission time Handle Problem Language Result Execution time Memory
1013815 2024-07-04T06:26:31 Z May27_th Bob (COCI14_bob) C++17
120 / 120
 108 ms 18108 KB 
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define i128 __int128
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(10);
  int Tests = 1; // cin >> Tests;
  while (Tests --) {
    int N, M; cin >> N >> M;
    vector<vector<int>> a(N + 2, vector<int> (M + 2, 0));
    vector<vector<int>> h(N + 2, vector<int> (M + 2, 0));
    vector<vector<i64>> f(N + 2, vector<i64> (M + 2, 0));
    for (int i = 1; i <= N; i ++) {
      for (int j = 1; j <= M; j ++) {
        cin >> a[i][j];
      }
    }
    for (int j = 1; j <= M; j ++) {
      for (int i = 1; i <= N; i ++) {
        if (a[i][j] != a[i - 1][j]) h[i][j] = 1;
        else h[i][j] = h[i - 1][j] + 1;
      }
    }
    i64 ans = 0;
    stack<int> st;
    for (int i = 1; i <= N; i ++) {
      while (!st.empty()) st.pop();
      for (int j = 1; j <= M; j ++) {
        if (a[i][j] != a[i][j - 1]) {
          while (!st.empty()) st.pop();
          f[i][j] = h[i][j];
          ans += f[i][j];
          h[i][j - 1] = 0;
          f[i][j - 1] = 0;
          st.push(j - 1);
          st.push(j);
          continue;
        }
        while (!st.empty() && h[i][st.top()] >= h[i][j]) st.pop();
        f[i][j] = f[i][st.top()] + (j - st.top()) * h[i][j];
        ans = ans + f[i][j];
        st.push(j);
      }
    }
    cout << ans << "\n";
  }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 16220 KB Output is correct
2 Correct 46 ms 18012 KB Output is correct
3 Correct 50 ms 18108 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 16260 KB Output is correct
2 Correct 48 ms 18068 KB Output is correct
3 Correct 46 ms 18040 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 16216 KB Output is correct
2 Correct 46 ms 18008 KB Output is correct
3 Correct 45 ms 18008 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 16264 KB Output is correct
2 Correct 46 ms 18040 KB Output is correct
3 Correct 45 ms 18000 KB Output is correct