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;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 1007;
const ll inf = 2e9;
const ll mod = 998244353;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;
ll Add(ll x, ll y){
x %= mod;
y %= mod;
return (x + y) % mod;
}
ll Mul(ll x, ll y){
x %= mod;
y %= mod;
return (x * y) % mod;
}
ll n, m, a[M][M], len[M][M], ans;
void rid(vector < pair <ll,ll> > v){
ll w = 0;
while(v.size()){
ans = Add(ans, Mul(w, Mul(v.back().F, v.back().S)));
w += v.back().S;
v.pop_back();
}
return;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) cin >> a[i][j];
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(a[i][j] == a[i - 1][j]) len[i][j] = len[i - 1][j] + 1;
else len[i][j] = 1;
}
}
for(int i = n; i; --i){
vector < pair <ll, ll> > v; //h, w
for(int j = 1; j <= m; ++j){
if(a[i][j] != a[i][j - 1]) rid(v), v.clear();
ll w = 0;
while(v.size() && v.back().F >= len[i][j]){
ans = Add(ans, Mul(w, Mul(v.back().F, v.back().S)));
w += v.back().S;
v.pop_back();
}
ans = Add(ans, Mul(w + 1, len[i][j]));
v.pb({len[i][j], w + 1});
}
rid(v);
}
cout << ans << endl;
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... |