Submission #987129

#	Time	Username	Problem	Language	Result	Execution time	Memory
987129		cig32	Rectangles (IOI19_rect)	C++17	0 / 100	7 ms	10588 KiB

rect

#include "rect.h"
#include "bits/stdc++.h"
using namespace std;
#define int long long

int32_t A[2500][2500];

int32_t upBad[2500][2500];
int32_t downBad[2500][2500];
int32_t leftBad[2500][2500];
int32_t rightBad[2500][2500];

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

  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      A[i][j] = a[i][j];
    }
  }
  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;
        }
      }
    }
  }
  int left[n][m], right[n][m], up[n][m], down[n][m];
  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      left[i][j] = leftBad[i][j];
      up[i][j] = upBad[i][j];
      right[i][j] = rightBad[i][j];
      down[i][j] = downBad[i][j];
    }
  }
  int ans = 0;
  for(int len=1; len<=n-2; len++) {
    if(len > 1) {
      for(int x=0; x<m; x++) {
        for(int i=0; i+len-1<n; i++) {
          right[i][x] = min(right[i][x], right[i+1][x]);
          left[i][x] = max(left[i][x], left[i+1][x]);
          up[i][x] = max(up[i][x], up[i][x+1]);
          down[i][x] = min(down[i][x], down[i][x+1]);
        }
      }
    }
    for(int i=1; i+len-1<=n-2; i++) {
      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[i][x - 1] - 1;
        if(u <= d && l <= r) {
          alive = 1;
          alive &= (right[u][l - 1] > r);
          alive &= (left[u][r + 1] < l);
          alive &= (down[u - 1][l] > d);
          alive &= (up[d + 1][l] < u);
          ans += alive;
          //if(alive) cout << "u = " << u << ", d = " << d << ", l = " << l << ", r = "<<r<<"\n";
        }
        // as right
        l = left[i][x + 1] + 1, r = x;
        
        if(u <= d && l <= r) {
          alive = 1;
          alive &= (right[u][l - 1] > r);
          alive &= (left[u][r + 1] < l);
          alive &= (down[u - 1][l] > d);
          alive &= (up[d + 1][l] < u);
          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

*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28