Submission #577134

#	Time	Username	Problem	Language	Result	Execution time	Memory
577134		MilosMilutinovic	Bob (COCI14_bob)	C++14	120 / 120	244 ms	43040 KiB

bob

#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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12