oj.uz

Submission #577134

# Submission time Handle Problem Language Result Execution time Memory
577134 2022-06-14T07:23:51 Z MilosMilutinovic Bob (COCI14_bob) C++14
120 / 120
 244 ms 43040 KB 
#include <bits/stdc++.h>

using namespace std;

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];
    }
  }
  vector<int> xs;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      xs.push_back(a[i][j]);
    }
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      a[i][j] = lower_bound(xs.begin(), xs.end(), a[i][j]) - xs.begin();
    }
  }
  int k = xs.size();
  vector<vector<int>> at(k);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      at[a[i][j]].push_back(i * m + j);
    }
  }
  vector<vector<int>> f(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (i == 0 || a[i][j] != a[i - 1][j]) {
        f[i][j] = 1;
      } else {
        f[i][j] = f[i - 1][j] + 1;
      }
    }
  }
  vector<vector<int>> l(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (j == 0 || a[i][j] != a[i][j - 1]) {
        l[i][j] = i * m + j;
      } else {
        l[i][j] = l[i][j - 1];
      }
    }
  }
  vector<vector<long long>> dp(n, vector<long long>(m));
  for (int v = 0; v < k; v++) {
    vector<int> stk;
    for (int id : at[v]) {
      int i = id / m;
      int j = id % m;
      if (!stk.empty() && stk.back() < l[i][j]) {
        stk.clear();
      }
      while (!stk.empty()) {
        int ii = stk.back() / m;
        int jj = stk.back() % m;
        if (f[i][j] < f[ii][jj]) {
          stk.pop_back();
        } else {
          break;
        }
      }
      if (!stk.empty()) {
        int x = stk.back() / m;
        int y = stk.back() % m;
        dp[i][j] += dp[x][y];
      }
      int p = (stk.empty() ? (l[i][j] % m) - 1 : stk.back() % m);
      dp[i][j] += f[i][j] * (j - p);
      stk.push_back(id);
    }
  }
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    ans += accumulate(dp[i].begin(), dp[i].end(), 0LL);
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 41344 KB Output is correct
2 Correct 130 ms 29844 KB Output is correct
3 Correct 100 ms 29944 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 43040 KB Output is correct
2 Correct 125 ms 30200 KB Output is correct
3 Correct 100 ms 29820 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 42960 KB Output is correct
2 Correct 111 ms 29684 KB Output is correct
3 Correct 98 ms 29668 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 42504 KB Output is correct
2 Correct 102 ms 29836 KB Output is correct
3 Correct 98 ms 29680 KB Output is correct