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;
typedef long long LL;
int const N = 1005;
int a[N][N];
int color[N], cnt[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
}
}
LL ans = 0;
for(int i = 1; i <= n; i++){
int c = 0;
vector<pair<int, int> > stk;
stk.push_back({0, 0});
for(int j = 1; j <= m; j++){
if(color[j] == a[i][j]){
cnt[j]++;
}else{
cnt[j] = 1;
color[j] = a[i][j];
}
if(color[j] != c){
while(stk.size() > 1){
int sc = stk.size() - 2;
ans += ((j - stk[sc].second - 1) * (j - stk[sc].second - 2) / 2 + j - stk[sc].second - 1) * (stk.back().first - stk[sc].first);
stk.pop_back();
}
stk.back().second = j - 1;
c = color[j];
stk.push_back({cnt[j], j});
}else{
while(stk.back().first >= cnt[j]){
if(stk.back().first > cnt[j]){
int sc = stk.size() - 2;
ans += ((j - stk[sc].second - 1) * (j - stk[sc].second - 2) / 2 + j - stk[sc].second - 1) * (stk.back().first - max(cnt[j], stk[sc].first));
}
stk.pop_back();
}
stk.push_back({cnt[j], j});
}
}
while(stk.size() > 1){
int sc = stk.size() - 2;
ans += ((m - stk[sc].second) * (m - stk[sc].second - 1) / 2 + m - stk[sc].second) * (stk.back().first - stk[sc].first);
stk.pop_back();
}
}
cout << ans << '\n';
}
# | 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... |