oj.uz

Submission #987233

# Submission time Handle Problem Language Result Execution time Memory
987233 2024-05-22T11:56:20 Z cig32 Rectangles (IOI19_rect) C++17
10 / 100
 26 ms 42480 KB 
#include "rect.h"
#include "bits/stdc++.h"
using namespace std;
#define int long long


const int MAXN = 2500;
int32_t upBad[MAXN][MAXN];
int32_t downBad[MAXN][MAXN];
int32_t leftBad[MAXN][MAXN];
int32_t rightBad[MAXN][MAXN];

int32_t up[MAXN][12][MAXN], down[MAXN][12][MAXN];
int32_t Left[MAXN][12][MAXN], Right[MAXN][12][MAXN];

int n,m;

int up_query(int i, int l, int r) {
  int k = 32 - __builtin_clz(r - l + 1) - 1;
  return max(up[i][k][l], up[i][k][r - (1<<k) + 1]);
}

int down_query(int i, int l, int r) {
  int k = 32 - __builtin_clz(r - l + 1) - 1;
  return min(down[i][k][l], down[i][k][r - (1<<k) + 1]);
}

int left_query(int i, int l, int r) {
  int k = 32 - __builtin_clz(r - l + 1) - 1;
  return max(Left[i][k][l], Left[i][k][r - (1<<k) + 1]);
}

int right_query(int i, int l, int r) {
  int k = 32 - __builtin_clz(r - l + 1) - 1;
  return min(Right[i][k][l], Right[i][k][r - (1<<k) + 1]);
}

int count_rectangles(std::vector<std::vector<int32_t> > a) {
	
  n = a.size(), m = a[0].size();

  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      rightBad[i][j] = m;
      downBad[i][j] = n;
      upBad[i][j] = -1;
      leftBad[i][j] = -1;
      for(int k=j+1; k<m; k++) {
        if(a[i][k] >= a[i][j]) {
          rightBad[i][j] = k; break;
        }
      }
      for(int k=j-1; k>=0; k--) {
        if(a[i][k] >= a[i][j]) {
          leftBad[i][j] = k; break;
        }
      }
      for(int k=i+1; k<n; k++) {
        if(a[k][j] >= a[i][j]) {
          downBad[i][j] = k; break;
        }
      }
      for(int k=i-1; k>=0; k--) {
        if(a[k][j] >= a[i][j]) {
          upBad[i][j] = k; break;
        }
      }
    }
  }
  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      Left[j][0][i] = leftBad[i][j];
      Right[j][0][i] = rightBad[i][j];
      up[i][0][j] = upBad[i][j];
      down[i][0][j] = downBad[i][j];
    }
  }

  for(int k=1; k<12; k++) {
    for(int i=0; i<n; i++) {
      for(int j=0; j+(1<<k)-1<m; j++) {
        up[i][k][j] = max(up[i][k-1][j], up[i][k-1][j+(1<<(k-1))]);
        down[i][k][j] = min(down[i][k-1][j], down[i][k-1][j+(1<<(k-1))]);
      }
    }
    for(int i=0; i<m; i++) {
      for(int j=0; j+(1<<k)-1<n; j++) {
        Left[i][k][j] = max(Left[i][k-1][j], Left[i][k-1][j+(1<<(k-1))]);
        Right[i][k][j] = min(Right[i][k-1][j], Right[i][k-1][j+(1<<(k-1))]);
      }
    }
  }
  
  int ans = 0;
  for(int len=1; len<=n-2; len++) {
    for(int i=1; i+len-1<=n-2; i++) {
      int sto[m];
      for(int x=1; x+1<m; x++) {
        int u, d, l, r;
        bool alive;
        u = i, d = i + len - 1;
        // as left
        l = x, r = right_query(x - 1, u, d) - 1;
        sto[l] = r;
        if(u <= d && l <= r) {
          alive = 1;
          alive &= (right_query(l - 1, u, d) > r);
          alive &= (left_query(r + 1, u, d) < l);
          alive &= (down_query(u - 1, l, r) > d);
          alive &= (up_query(d + 1, l, r) < u);
          for(int i=u; i<=d; i++) {
            for(int j=l; j<=r; j++) {
              alive &= (a[i][j] < a[u-1][j]);
              alive &= (a[i][j] < a[d+1][j]);
              alive &= (a[i][j] < a[i][l-1]);
              alive &= (a[i][j] < a[i][r+1]);
            }
          }
          ans += alive;
          //if(alive) cout << "u = " << u << ", d = " << d << ", l = " << l << ", r = "<<r<<"\n";
        }
        // as right
        l = left_query(x + 1, u, d) + 1, r = x;
        
        if(u <= d && l <= r ) {
          alive = 1;
          alive &= (right_query(l - 1, u, d) > r);
          alive &= (left_query(r + 1, u, d) < l);
          alive &= (down_query(u - 1, l, r) > d);
          alive &= (up_query(d + 1, l, r) < u);
          for(int i=u; i<=d; i++) {
            for(int j=l; j<=r; j++) {
              alive &= (a[i][j] < a[u-1][j]);
              alive &= (a[i][j] < a[d+1][j]);
              alive &= (a[i][j] < a[i][l-1]);
              alive &= (a[i][j] < a[i][r+1]);
            }
          }
          ans += alive;
          //if(alive) cout << "u = " << u << ", d = " << d << ", l = " << l << ", r = "<<r<<"\n";
        }
      }
    }
  }
  

  return ans;
}

/*
g++ -std=c++17 -O2 -o rect grader.cpp rect.cpp
./rect < input.txt

*/

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:97:11: warning: variable 'sto' set but not used [-Wunused-but-set-variable]
   97 |       int sto[m];
      |           ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42480 KB Output is correct
2 Correct 25 ms 36184 KB Output is correct
3 Correct 21 ms 42328 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 18 ms 42400 KB Output is correct
6 Correct 22 ms 42332 KB Output is correct
7 Correct 21 ms 42332 KB Output is correct
8 Correct 25 ms 42348 KB Output is correct
9 Correct 22 ms 42328 KB Output is correct
10 Correct 11 ms 21848 KB Output is correct
11 Correct 19 ms 42076 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -