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>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=1005;
int f[N][N], m, n, a[N][N], luu[N], dem, rmq[N][12];
long long ans;
int getmin(int i, int j) {
int leng=j-i+1;
int logg=log2(leng);
return min(rmq[i][logg], rmq[j-(1ll<<logg)+1][logg]);
}
void tinh() {
rep(i, 1, dem) rmq[i][0]=luu[i];
rep(i, 1, 10)
for(int j=1 ; j+(1ll<<i)-1<=dem ; ++j) {
rmq[j][i]=min(rmq[j][i-1], rmq[j+(1ll<<(i-1))][i-1]);
}
rep(i, 1, dem) {
rep(val, 1, luu[i]) {
int r=dem+1, l=i;
while(r-l>1) {
int mid=(r+l)>>1;
if(getmin(i, mid)<val) r=mid;
else l=mid;
}
ans+=r-i;
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen(Task".inp", "r", stdin);
//freopen(Task".out", "w", stdout);
cin >> m >> n;
rep(i, 1, m)
rep(j, 1, n) {
cin >> a[i][j];
f[i][j]=1;
if(a[i-1][j]==a[i][j]) f[i][j]+=f[i-1][j];
}
rep(i, 1, m) {
int ptr=1;
a[i][n+1]=-1;
while(ptr<=n) {
int j=ptr;
dem=0;
for( ; j<=n ; ++j) {
luu[++dem]=f[i][j];
if(a[i][j]!=a[i][j+1]) {
tinh();
break;
}
}
ptr=j+1;
}
}
cout << ans;
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... |