이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
static int verif(int i, int j, int ii, int jj){
if(i == 0 || j == 0 || i == ii - 1 || j == jj - 1){
return 0;
}
if(lst[i][j] == ii * 2500 + jj){
return 0;
}
lst[i][j] = ii * 2500 + jj;
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];
col[i + 1][ c[u] ].push_back(j);
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]);
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];
lin[ c[u] ][j + 1].push_back(i);
c[++u] = i;
}
}
for(ii = 0; ii < 2; ii++){
for(i = 1; i <= n; i++){
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(ii = 2; ii < 4; ii++){
for(j = 1; j <= m; j++){
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(ii = 0; ii < lin[i][j].size(); ii++){
for(jj = 0; jj < col[i][j].size(); jj++){
sol += verif(lin[i][j][ii], col[i][j][jj], i, j);
}
}
}
}
return sol;
}
컴파일 시 표준 에러 (stderr) 메시지
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:108:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(ii = 0; ii < lin[i][j].size(); ii++){
| ~~~^~~~~~~~~~~~~~~~~~
rect.cpp:109:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(jj = 0; jj < col[i][j].size(); jj++){
| ~~~^~~~~~~~~~~~~~~~~~
# | 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... |