Submission #204414

#	Time	Username	Problem	Language	Result	Execution time	Memory
204414		ADJA	Rectangles (IOI19_rect)	C++14	38 / 100	646 ms	122872 KiB

rect

#include "rect.h"
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
 
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
 
using namespace std;

const int MAXN = 2500;

int n, m;
int a[MAXN][MAXN];
int ok[MAXN][MAXN];
int mxc[MAXN];

int one[MAXN][MAXN], zero[MAXN][MAXN];

long long solveSix() {
  for (int j = m - 1; j >= 0; j--) {
    for (int i = 0; i < n; i++) {
      if (a[i][j] == 0) {
        one[i][j] = 0;
        zero[i][j] = 1 + zero[i][j + 1];
      } else {
        zero[i][j] = 0;
        one[i][j] = 1 + one[i][j + 1];
      }
    }
  }

  long long ans = 0;
  for (int j = 0; j + 1 < m; j++) {
    int prevOne = -1, mnZero = 123123, mxZero = -1;
    for (int i = 0; i < n; i++) {
      if (a[i][j] == 1 && one[i][j + 1] == 0) {
        mxZero = max(mxZero, zero[i][j + 1]);
        mnZero = min(mnZero, zero[i][j + 1]);
      } else {
        int curOne = one[i][j + 1];
        if (prevOne != -1 && mxZero != -1 && mxZero == mnZero) {
          int zeroLen = mnZero;
          if (j + zeroLen + 1 < m && prevOne >= zeroLen && curOne >= zeroLen) {
            ans++;
            // cerr << i << " " << j << endl;
          }
        }
        prevOne = curOne;
        mnZero = 123123, mxZero = -1;
      }
    }
  }

  return ans;
}

long long count_rectangles(std::vector<std::vector<int> > A) {
  n = sz(A); m = sz(A[0]);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      a[i][j] = A[i][j];
    }
  }

  bool isSix = true;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (a[i][j] > 1) {
        isSix = false;
      }
    }
  }
  if (isSix) {
    return solveSix();
  }

  long long ans = 0;
  vector<int> cols;
  for (int i = 0; i < m; i++) {
    cols.push_back(i);
  }
  random_shuffle(all(cols));

  int lim = min(100, m);
  if (n <= 3) {
    lim = m;
  }
  for (int coli = 0; coli < lim; coli++) {
    int col = cols[coli];
    if (col == m - 1) {
      continue;
    }
    for (int i = 0; i < n; i++) {
      for (int j = col; j < m; j++) {
        ok[i][j] = 0;
      }
    }
    for (int i = 0; i < n; i++) {
      int mx = -1;
      for (int j = col + 1; j < m; j++) {
        if (a[i][col] > mx && a[i][j] > mx) {
          ok[i][j] = 1;
        }
        if (a[i][j] > mx) {
          mx = a[i][j];
        }
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = col + 1; j < m; j++) {
        if (ok[i][j]) {
          ok[i][j] = 1 + ok[i - 1][j];
        }
      }
    }

    for (int row = 0; row + 1 < n; row++) {
      for (int j = col + 1; j < m; j++) {
        mxc[j] = -1;
      }
      for (int row2 = row + 1; row2 < n; row2++) {
        bool good = true;
        for (int col2 = col + 1; col2 + 1 < m; col2++) {
          if (!(a[row][col2] > mxc[col2] && a[row2][col2] > mxc[col2])) {
            good = false;
          }
          if (good && row2 - 1 > row && ok[row2 - 1][col2 + 1] >= row2 - row - 1) {
            ans++;
          }
          if (a[row2][col2] > mxc[col2]) {
            mxc[col2] = a[row2][col2];
          }
        }
      }
    }
  }

  return ans;
}

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