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>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
const int N = 15013;
const int SQ = 240;
int a[200013];
int b[200013];
bool f[200013];
int s[200013];
int h, w;
inline int id(int i, int j){
return i * (w + 1) + j;
}
inline int id2(int i, int j){
return j * (h + 1) + i;
}
inline int qry(int x1, int x2, int y1, int y2){
return s[id(x2 + 1, y2 + 1)] + s[id(x1, y1)] - s[id(x2 + 1, y1)] - s[id(x1, y2 + 1)];
}
struct PartialSum2D{
vector<vector<short>> a, ps;
PartialSum2D() = default;
PartialSum2D(int n, int m){
a = ps = vector<vector<short>>(n + 1, vector<short>(m + 1));
}
void upd(int x1, int x2, int y1, int y2, int v){
a[x2 + 1][y2 + 1] += v;
a[x1][y2 + 1] -= v;
a[x2 + 1][y1] -= v;
a[x1][y1] += v;
}
void run(int n){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + a[i - 1][j - 1];
}
}
}
int qry(int x, int y){
return ps[x + 1][y + 1];
}
};
int32_t main(){
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
cin >> h >> w;
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
cin >> a[id(i, j)];
}
}
if(h > w){
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
b[id2(i, j)] = a[id(i, j)];
}
}
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
a[id2(i, j)] = b[id2(i, j)];
}
}
swap(w, h);
}
{
set<int> S; map<int, int> M;
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
S.insert(a[id(i, j)]);
}
}
int idx = 0;
for(auto j : S){
M[j] = idx++;
}
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
a[id(i, j)] = M[a[id(i, j)]];
}
}
}
PartialSum2D ps[h][h];
for(int x1 = 0; x1 < h; x1++){
for(int x2 = x1; x2 < h; x2++){
ps[x1][x2] = PartialSum2D(w, w);
}
}
int ans = 0;
for(int i = 0; i < h; i++){
for(int j = 0; j < w - 1; j++){
int v1 = a[id(i, j)], v2 = a[id(i, j + 1)];
if(v1 > v2) swap(v1, v2);
for(int x = 0; x < h; x++){
for(int y = 0; y < w; y++){
f[id(x, y)] = a[id(x, y)] > v1 && a[id(x, y)] < v2;
}
}
for(int x = 0; x < h; x++){
for(int y = 0; y < w; y++){
s[id(x + 1, y + 1)] = s[id(x + 1, y)] + s[id(x, y + 1)] - s[id(x, y)] + f[id(x, y)];
}
}
int x1 = i, x2 = i, y1 = j, y2 = j + 1;
for(int x3 = 0; x3 <= x1; x3++){
int y3 = 0, y4 = w - 1;
for(int x4 = x2; x4 < h; x4++){
if(qry(x3, x4, y1, y2)) continue;
while(qry(x3, x4, y3, y1)) y3++;
while(qry(x3, x4, y2, y4)) y4--;
ps[x3][x4].upd(y3, y1, y2, y4, 1);
}
}
}
}
for(int i = 0; i < h - 1; i++){
for(int j = 0; j < w; j++){
int v1 = a[id(i, j)], v2 = a[id(i + 1, j)];
if(v1 > v2) swap(v1, v2);
for(int x = 0; x < h; x++){
for(int y = 0; y < w; y++){
f[id(x, y)] = a[id(x, y)] > v1 && a[id(x, y)] < v2;
}
}
for(int x = 0; x < h; x++){
for(int y = 0; y < w; y++){
s[id(x + 1, y + 1)] = s[id(x + 1, y)] + s[id(x, y + 1)] - s[id(x, y)] + f[id(x, y)];
}
}
int x1 = i, x2 = i + 1, y1 = j, y2 = j;
for(int x3 = 0; x3 <= x1; x3++){
int y3 = 0, y4 = w - 1;
for(int x4 = x2; x4 < h; x4++){
if(qry(x3, x4, y1, y2)) continue;
while(qry(x3, x4, y3, y1)) y3++;
while(qry(x3, x4, y2, y4)) y4--;
ps[x3][x4].upd(y3, y1, y2, y4, 1);
}
}
}
}
for(int x1 = 0; x1 < h; x1++){
for(int x2 = x1; x2 < h; x2++){
ps[x1][x2].run(w);
for(int y1 = 0; y1 < w; y1++){
for(int y2 = y1; y2 < w; y2++){
ans += ps[x1][x2].qry(y1, y2) == (x2 - x1 + 1) * (y2 - y1 + 1) - 1;
}
}
}
}
cout << ans << endl;
}
# | 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... |