| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 624840 | QwertyPi | Sandcastle 2 (JOI22_ho_t5) | C++14 | 0 ms | 0 KiB |
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")
#pragma GCC optimize("avx2")
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;
int id(int i, int j){
return i * (w + 1) + j;
}
int id2(int i, int j){
return j * (h + 1) + i;
}
struct Range{
short x1, x2, y1, y2; // 1D; [x1, x2] x [y1, y2]
};
vector<Range> vrs[SQ][SQ];
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{
short a[N][N] = {0}, ps[N][N] = {0};
void clear(int n){
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
a[i][j] = ps[i][j] = 0;
}
}
}
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];
}
} ps;
int g(vector<Range>& vr, int h){
ps.clear(w);
for(auto r : vr){
ps.upd(r.x1, r.x2, r.y1, r.y2, 1);
}
ps.run(w);
int ans = 0;
for(int i = 0; i < w; i++){
for(int j = i; j < w; j++){
ans += ps.qry(i, j) == h * (j - i + 1) - 1;
}
}
return ans;
}
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)]];
}
}
}
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--;
vrs[x3][x4].emplace_back({y3, y1, y2, y4});
}
}
}
}
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--;
vrs[x3][x4].emplace_back({y3, y1, y2, y4});
}
}
}
}
for(int x1 = 0; x1 < h; x1++){
for(int x2 = x1; x2 < h; x2++){
ans += g(vrs[x1][x2], x2 - x1 + 1);
}
}
cout << ans << endl;
}