| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 229705 | combi1k1 | Rectangles (IOI19_rect) | 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 "rectangles.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define pb emplace_back
#define X first
#define Y second
const int N = 2e5 + 5;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<vi> mtx;
typedef pair<ii,ii> rec;
ll count_rectangles(mtx A) {
int n = sz(A);
int m = sz(A[0]);
mtx l(n,vi(m,m + 5));
mtx u(n,vi(m,n + 5));
mtx r(n,vi(m,-5));
mtx d(n,vi(m,-5));
for(int i = 0 ; i < n ; ++i) {
stack<int> lef;
stack<int> rig;
for(int j = 0 ; j < m ; ++j) {
while (lef.size() && A[i][lef.top()] < A[i][j])
lef.pop();
if (lef.size()) l[i][j] = lef.top();
lef.push(j);
}
for(int j = m - 1 ; j >= 0 ; --j) {
while (rig.size() && A[i][rig.top()] < A[i][j])
rig.pop();
if (rig.size()) r[i][j] = rig.top();
rig.push(j);
}
}
for(int j = 0 ; j < m ; ++j) {
stack<int> lef;
stack<int> rig;
for(int i = 0 ; i < n ; ++i) {
while (lef.size() && A[lef.top()][j] < A[i][j])
lef.pop();
if (lef.size()) u[i][j] = lef.top();
lef.push(i);
}
for(int i = n - 1 ; i >= 0 ; --i) {
while (rig.size() && A[rig.top()][j] < A[i][j])
rig.pop();
if (rig.size()) d[i][j] = rig.top();
rig.push(i);
}
}
mtx f[4];
f[0].assign(n,vi(m,-1));
f[1].assign(n,vi(m,-1));
f[2].assign(n,vi(m,-1));
f[3].assign(n,vi(m,-1));
for(int i = 0 ; i < n ; ++i)
for(int j = 0 ; j < m ; ++j) {
if (i == 0)
f[0][i][j] = (l[i][j] < 0),
f[1][j][j] = (r[i][j] < 0);
else {
if (l[i][j] < 0) f[0][i][j] = i + 1;
else {
if (l[i - 1][j] == l[i][j]) f[0][i][j] = f[0][i - 1][j];
else if (r[i - 1][l[i][j]] == j) f[0][i][j] = f[1][i - 1][l[i][j]];
else f[0][i][j] = i;
}
if (r[i][j] < 0) f[1][i][j] = i + 1;
else {
if (r[i - 1][j] == r[i][j]) f[1][i][j] = f[1][i - 1][j];
else if (l[i - 1][r[i][j]] == j) f[1][i][j] = f[0][i - 1][r[i][j]];
else f[1][i][j] = i;
}
}
}
for(int j = 0 ; j < m ; ++j)
for(int i = 0 ; i < n ; ++i) {
if (j == 0)
f[2][i][0] = (u[i][j] < 0),
f[3][i][0] = (d[i][j] < 0);
else {
if (u[i][j] < 0) f[2][i][j] = i + 1;
else {
if (u[i][j - 1] == u[i][j]) f[2][i][j] = f[2][i][j - 1];
else if (d[u[i][j]][j - 1] == i) f[2][i][j] = f[3][u[i][j]][j - 1];
else f[2][i][j] = j;
}
if (r[i][j] < 0) f[1][i][j] = i + 1;
else {
if (d[i][j - 1] == d[i][j]) f[3][i][j] = f[3][i][j - 1];
else if (u[d[i][j]][j - 1] == i) f[3][i][j] = f[2][d[i][j]][j - 1];
else f[3][i][j] = j;
}
}
}
set<rec> ans;
auto check = [&](int L,int R,int U,int D) {
if (L > R || U > D) return;
if (L < 1 || R > n - 2) return;
if (U < 1 || D > n - 2) return;
if (u[R + 1][D] != L - 1 && d[L - 1][D] != R + 1) return;
if (l[R][D + 1] != U - 1 && r[R][U - 1] != D + 1) return;
if (A[R][U - 1] >= A[R][D + 1] && f[0][R][D + 1] > L) return;
if (A[R][U - 1] <= A[R][D + 1] && f[1][R][U - 1] > L) return;
if (A[L - 1][D] >= A[R + 1][D] && f[2][R + 1][D] > U) return;
if (A[L - 1][D] <= A[R + 1][D] && f[3][L - 1][D] > U) return;
ans.insert(rec(ii(L,R),ii(U,D)));
};
for(int i = 1 ; i < n - 1 ; ++i)
for(int j = 1 ; j < m - 1 ; ++j) {
check(u[i + 1][j] + 1,i,l[i][j + 1] + 1,j);
check(u[i + 1][j] + 1,i,j,r[i][j - 1] - 1);
check(i,d[i - 1][j] - 1,l[i][j + 1] + 1,j);
check(i,d[i - 1][j] - 1,j,r[i][j - 1] - 1);
}
return ans.size();
}
/*int main() {
cerr << count_rectangles({ {4, 8, 7, 5, 6},
{7, 4, 10, 3, 5},
{9, 7, 20, 14, 2},
{9, 14, 7, 3, 6},
{5, 7, 5, 2, 7},
{4, 5, 13, 5, 6}});
}*/