이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#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 int n, m, nr;
struct str{
int a, b, c, d;
};
vector<str> w;
int cmp(str x, str y){
if(x.a != y.a){
return x.a < y.a;
}
if(x.b != y.b){
return x.b < y.b;
}
if(x.c != y.c){
return x.c < y.c;
}
return x.d < y.d;
}
static void 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 || ii == n + 1 || jj == m + 1){
return;
}
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) ){
w.push_back( {i, j, ii, jj} );
}
}
}
long long count_rectangles(std::vector<std::vector<int> > a1) {
int 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];
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];
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];
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];
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++){
verif(i, j, d[2][i][j - 1], d[0][i - 1][j]);
verif(i, j, d[2][i][j - 1], d[1][i - 1][j]);
verif(i, j, d[3][i][j - 1], d[0][i - 1][j]);
verif(i, j, d[3][i][j - 1], d[1][i - 1][j]);
verif(i, j, d[2][i][j - 1], d[0][i - 1][j]);
verif(i, j, d[2][i][j + 1], d[1][i - 1][j]);
verif(i, j, d[3][i][j + 1], d[0][i - 1][j]);
verif(i, j, d[3][i][j + 1], d[1][i - 1][j]);
verif(i, j, d[2][i][j - 1], d[0][i + 1][j]);
verif(i, j, d[2][i][j - 1], d[1][i + 1][j]);
verif(i, j, d[3][i][j - 1], d[0][i + 1][j]);
verif(i, j, d[3][i][j - 1], d[1][i + 1][j]);
verif(i, j, d[2][i][j - 1], d[0][i + 1][j]);
verif(i, j, d[2][i][j + 1], d[1][i + 1][j]);
verif(i, j, d[3][i][j + 1], d[0][i + 1][j]);
verif(i, j, d[3][i][j + 1], d[1][i + 1][j]);
}
}
sort(w.begin(), w.end(), cmp);
sol = 1;
for(i = 1; i < w.size(); i++){
if(w[i].a != w[sol - 1].a || w[i].b != w[sol - 1].b || w[i].c != w[sol - 1].c || w[i].d != w[sol - 1].d ){
w[++sol] = w[i];
}
}
return sol;
}
컴파일 시 표준 에러 (stderr) 메시지
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:143:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<str>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for(i = 1; i < w.size(); i++){
| ~~^~~~~~~~~~
rect.cpp:43:16: warning: unused variable 'jj' [-Wunused-variable]
43 | int i, j, ii, jj, u;
| ^~
rect.cpp: At global scope:
rect.cpp:8:18: warning: 'nr' defined but not used [-Wunused-variable]
8 | static int n, m, nr;
| ^~
rect.cpp:7:73: warning: 'lst' defined but not used [-Wunused-variable]
7 | 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... |