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<iostream>
#include<vector>
#include "rect.h"
using namespace std;
static int a[2505][2505], d[4][2505][2505], c[2505], df[4][2505][2505], lst[2505][2505];
static vector<int> lin[2505][2505], col[2505][2505], lin2[2505][2505];
static int verif(int i, int j, int ii, int jj){
if(i > ii){
swap(i, ii);
}
if(j > jj){
swap(j, jj);
}
if(i == 0 || j == 0 || i == ii - 1 || j == jj - 1){
return 0;
}
if( (d[0][ii - 1][jj] == j && df[0][ii - 1][jj] <= i + 1) || (d[1][ii - 1][j] == jj && df[1][ii - 1][j] <= i + 1) ){
if( (d[2][ii][jj - 1] == i && df[2][ii][jj - 1] <= j + 1) || (d[3][i][jj - 1] == ii && df[3][i][jj - 1] <= j + 1) ){
return 1;
}
}
return 0;
}
long long count_rectangles(std::vector<std::vector<int> > a1) {
int n, m, i, j, ii, jj, u;
long long sol = 0;
n = a1.size();
m = a1[0].size();
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
a[i][j] = a1[i - 1][j - 1];
}
}
for(i = 1; i <= n; i++){
u = 0;
c[0] = 0;
for(j = 1; j <= m; j++){
while(u > 0 && a[i][ c[u] ] < a[i][j]){
u--;
}
d[0][i][j] = c[u];
col[i + 1][j].push_back(c[u]);
c[++u] = j;
}
u = 0;
c[0] = m + 1;
for(j = m; j >= 1; j--){
while(u > 0 && a[i][ c[u] ] < a[i][j]){
u--;
}
d[1][i][j] = c[u];
if(a[i][j] < a[i][ c[u] ]){
col[i + 1][j].push_back(c[u]);
}
c[++u] = j;
}
}
for(j = 1; j <= m; j++){
u = 0;
c[0] = 0;
for(i = 1; i <= n; i++){
while(u > 0 && a[ c[u] ][j] < a[i][j]){
u--;
}
d[2][i][j] = c[u];
lin[i][j + 1].push_back(c[u]);
lin2[i][j - 1].push_back(c[u]);
c[++u] = i;
}
u = 0;
c[0] = n + 1;
for(i = n; i >= 1; i--){
while(u > 0 && a[ c[u] ][j] < a[i][j]){
u--;
}
d[3][i][j] = c[u];
if(a[ c[u] ][j] != a[i][j]){
lin[ c[u] ][j + 1].push_back(i);
lin2[ c[u] ][j - 1].push_back(i);
}
c[++u] = i;
}
}
for(i = 1; i <= n; i++){
for(ii = 0; ii < 2; ii++){
for(j = 1; j <= m; j++){
df[ii][i][j] = i;
if(d[ii][i - 1][j] == d[ii][i][j]){
df[ii][i][j] = df[ii][i - 1][j];
}
else if(d[1 - ii][i - 1][ d[ii][i][j] ] == j){
df[ii][i][j] = df[1 - ii][i - 1][ d[ii][i][j] ];
}
}
}
}
for(j = 1; j <= m; j++){
for(ii = 2; ii < 4; ii++){
for(i = 1; i <= n; i++){
df[ii][i][j] = j;
if(d[ii][i][j - 1] == d[ii][i][j]){
df[ii][i][j] = df[ii][i][j - 1];
}
else if(d[5 - ii][ d[ii][i][j] ][j - 1] == i){
df[ii][i][j] = df[5 - ii][ d[ii][i][j] ][j - 1];
}
}
}
}
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
for(jj = 0; jj < col[i][j].size(); jj++){
if(col[i][j][jj] < j){
for(ii = 0; ii < lin[i][j].size(); ii++){
sol += verif(i, j, lin[i][j][ii], col[i][j][jj]);
}
}
else{
for(ii = 0; ii < lin2[i][j].size(); ii++){
sol += verif(i, j, lin2[i][j][ii], col[i][j][jj]);
}
}
}
}
}
return sol;
}
Compilation message (stderr)
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:116:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(jj = 0; jj < col[i][j].size(); jj++){
| ~~~^~~~~~~~~~~~~~~~~~
rect.cpp:118:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(ii = 0; ii < lin[i][j].size(); ii++){
| ~~~^~~~~~~~~~~~~~~~~~
rect.cpp:123:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(ii = 0; ii < lin2[i][j].size(); ii++){
| ~~~^~~~~~~~~~~~~~~~~~~
rect.cpp: At global scope:
rect.cpp:5:73: warning: 'lst' defined but not used [-Wunused-variable]
5 | static int a[2505][2505], d[4][2505][2505], c[2505], df[4][2505][2505], lst[2505][2505];
| ^~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |