Submission #266618

#TimeUsernameProblemLanguageResultExecution timeMemory
266618alexandra_udristoiuRectangles (IOI19_rect)C++14
72 / 100
5101 ms991436 KiB
#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( (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][ c[u] ] != a[i][j]){ 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]; if(a[ c[u] ][j] != a[i][j]){ lin[ 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(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; }

Compilation message (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++){
      |                             ~~~^~~~~~~~~~~~~~~~~~
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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...