This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;
/*
#pragma comment(linker, "/STACK:256000000")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/
template <class T> inline T gcd(T a , T b) { return !a ? b : gcd(b % a , a); }
template <class T> inline T lcm(T a , T b) { return (a * b) / gcd(a , b) ; }
mt19937 rnd(time(0));
#define all(x) x.begin(), x.end()
#define debug(x) { cerr << #x << " = " << x << endl; }
struct node {
int cnt;
int value;
int sum;
long long res;
node(int _c, int _v, int _s, ll _r) {
cnt = _c;
value = _v;
sum = _s;
res = _r;
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> f(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> f[i][j];
}
}
long long ans = 0ll;
vector<vector<int>> dp(n, vector<int>(m));
for (int i = 0; i < n; i++) {
stack<node> TOT;
TOT.push(node(0, -1, 0, 0));
for (int j = 0; j < m; j++) {
dp[i][j] = 1;
if (i > 0 && f[i - 1][j] == f[i][j]) {
dp[i][j] += dp[i - 1][j];
}
int down = 1;
while (TOT.top().value == f[i][j] && TOT.top().sum >= dp[i][j]) {
down += TOT.top().cnt;
TOT.pop();
}
long long cur = down * 1ll * dp[i][j];
if (TOT.top().value == f[i][j]) {
cur += TOT.top().res;
}
ans += cur;
TOT.push(node(down, f[i][j], dp[i][j], cur));
}
}
cout << ans << '\n';
return;
}
signed main() {
ios_base :: sync_with_stdio(0);
cin.tie(0) , cout.tie(0);
int t = 1;
while (t--) {
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |