| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 766858 | t6twotwo | Rectangles (IOI19_rect) | C++17 | 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 "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct T {
int L, R, U, D;
T() {
L = U = -1;
R = D = 2500;
}
T(int x, int y, int z, int t) {
L = x;
R = y;
U = z;
D = t;
}
};
T F(T &a, T &b) {
return {max(a.L, b.L), min(a.R, b.R), max(a.U, b.U), min(a.D, b.D)};
}
vector<int> ms(vector<int> &a, bool f) {
int n = a.size();
vector<int> b(n, f ? n : -1), stk;
for (int i = (f ? n - 1 : 0); i != (f ? -1 : n); i += (f ? -1 : 1)) {
while (!stk.empty() && a[stk.back()] < a[i]) {
stk.pop_back();
}
if (!stk.empty()) {
b[i] = stk.back();
}
stk.push_back(i);
}
return b;
}
int lg[2501];
T SX[2500][2500][12];
T SY[2500][2500][12];
T xquery(int x, int l, int r) {
if (l == r) {
return T();
}
int k = lg[r - l];
return F(SX[x][l][k], SX[x][r - (1 << k)][k]);
}
T yquery(int y, int l, int r) {
if (l == r) {
return T();
}
int k = lg[r - l];
return F(SY[y][l][k], SY[y][r - (1 << k)][k]);
}
ll count_rectangles(vector<vector<int>> a) {
for (int i = 2; i <= 2500; i++) {
lg[i] = lg[i / 2] + 1;
}
int n = a.size();
int m = a[0].size();
bool subtask6 = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] > 1) {
subtask6 = 0;
}
}
}
int ans = 0;
if (subtask6) {
vector pfs(n, vector<int>(m + 1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
pfs[i][j + 1] = pfs[i][j] + a[i][j];
}
}
vector<int> Q(n);
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
Q[i] = a[i][j] == 0 ? Q[i] + 1 : 0;
}
if (j == 0 || j == m - 1) {
continue;
}
for (int i = 1, k = 1; i < n - 1; i = k) {
while (k < n - 1 && (Q[i] == Q[k] && a[i][j + 1] == a[k][j + 1])) {
k++;
}
if (Q[i] > 0 && a[i][j + 1] == 1 && j - Q[i] >= 0 && pfs[i - 1][j + 1] - pfs[i - 1][j - Q[i] + 1] == Q[i] && pfs[k][j + 1] - pfs[k][j - Q[i] + 1] == Q[i]) {
ans++;
}
}
}
return ans;
}
T S[n][m]{};
for (int i = 0; i < n; i++) {
auto l = ms(a[i], 0);
auto r = ms(a[i], 1);
for (int j = 0; j < m; j++) {
S[i][j].L = l[j];
S[i][j].R = r[j];
}
}
for (int j = 0; j < m; j++) {
vector<int> v(n);
for (int i = 0; i < n; i++) {
v[i] = a[i][j];
}
auto u = ms(v, 0);
auto d = ms(v, 1);
for (int i = 0; i < n; i++) {
S[i][j].U = u[i];
S[i][j].D = d[i];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
SX[i][j][0] = S[i][j];
}
for (int j = 0; j < lg[m]; j++) {
for (int k = 0; k < (2 << j) <= m; k++) {
SX[i][k][j + 1] = F(SX[i][k][j], SX[i][k + (1 << j)][j]);
}
}
}
for (int i = 0; i < m; i++) {
vector<int> l(n), r(n);
for (int j = 0; j < n; j++) {
SY[i][j][0] = S[j][i];
}
for (int j = 0; j < lg[n]; j++) {
for (int k = 0; k < (2 << j) <= n; k++) {
SY[i][k][j + 1] = F(SY[i][k][j], SY[i][k + (1 << j)][j]);
}
}
}
auto check = [&](int x1, int y1, int x2, int y2) -> int {
if (x1 > x2 || y1 > y2 || x1 < 1 || y1 < 1 || x2 >= n - 1 || y2 >= m - 1) {
return 0;
}
if (xquery(x1 - 1, y1, y2 + 1).D <= x2) {
return 0;
}
if (xquery(x2 + 1, y1, y2 + 1).U >= x1) {
return 0;
}
if (yquery(y1 - 1, x1, x2 + 1).R <= y2) {
return 0;
}
if (yquery(y2 + 1, x1, x2 + 1).L >= y1) {
return 0;
}
return 1;
};
vector Q(n, vector<vector<int>>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (S[i][j].U != -1) {
Q[S[i][j].U][j].push_back(i);
}
}
}
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < m - 1; j++) {
int y = S[i][j - 1].R - 1;
if (y != m - 1) {
int x = S[i - 1][j].D - 1;
if (x != n - 1) {
ans += check(i, j, x, y);
}
for (int k : Q[i - 1][j]) {
if (a[i - 1][j] != a[k][j]) {
ans += check(i, j, k - 1, y);
}
}
}
y = S[i][j + 1].L + 1;
if (y != 0 && a[i][j + 1] != a[i][y - 1]) {
int x = S[i - 1][j].D - 1;
if (x != n - 1) {
ans += check(i, y, x, j);
}
for (int k : Q[i - 1][j]) {
if (a[i - 1][j] != a[k][j]) {
ans += check(i, y, k - 1, j);
}
}
}
}
}
return ans;
}