\(H, W \leq 3,000\) であるから，\(O(HW)\) は間に合う． 升目を全探索できるので，その上で穴の無い正方形を高速に数える．
升目 \(\,(x,y)\,\) を固定したとき，\( (x,y) \) を左上とする正方形のうち， 穴の無いものを数えたい． これは単調性があると分かる．すなわち， \(n \leq m\) かつ 長さ\(n\) の正方形に穴が有る ならば，長さ \(m\) の正方形にも穴がある． よって，binary search などが使えそうである．
左上のマスと一辺の長さを指定したとき，その正方形の内部に 穴が有るのかを高速に判定したい． つまり，正方形の内部にある穴の個数が分かれば十分なので， これは累積和で判定できる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
// 40 min
ll h,w,n ; cin >> h >> w >> n;
vll a(n), b(n);
vvll s(h+1, vll(w+1));
vvll ng(h, vll(w));
rep(i,n){
cin >> a[i] >> b[i];
a[i]--, b[i]--;
s[a[i]+1][b[i]+1] = 1;
ng[a[i]][b[i]] = true;
}
rep(x,h) rep(y,w){
s[x+1][y+1] += s[x][y+1] + s[x+1][y] - s[x][y];
}
ll ans = 0;
rep(x,h) rep(y,w) if(!ng[x][y]){
ll ok, ng;
ok = 0, ng = max(h,w)+5; // rem: max(h,w): (not n)
while(abs(ok-ng) > 1){
ll md = (ok + ng)/2;
ll nx = x + md;
ll ny = y + md;
bool f = true;
f &= in(nx,h+1);
f &= in(ny,w+1);
if(f){
ll cnt = s[nx][ny] - s[nx][y] - s[x][ny] + s[x][y];
assert(cnt >= 0);
f &= (cnt == 0);
}
if(f) ok = md;
else ng = md;
}
ans += ok;
}
cout << ans << endl;
return 0;
}
