Submission #155470

#	Time	Username	Problem	Language	Result	Execution time	Memory
155470		flashmt	Rectangles (IOI19_rect)	C++17	23 / 100	254 ms	99064 KiB

rect

#include <bits/stdc++.h>
using namespace std;
const int N = 2525;

int m, n, sum[N][N], isGood[N][N], a[N][N];
vector<pair<int, int>> intervals;
int maxRow[777][777][11], maxCol[777][777][11], lg2[N];

void init()
{
  for (int i = 1; i <= m; i++)
  {
    for (int j = 1; j <= n; j++)
      maxRow[i][j][0] = a[i][j];
    for (int lg = 0; lg < 9; lg++)
      for (int j = 1; j + (1 << lg + 1) - 1 <= n; j++)
        maxRow[i][j][lg + 1] = max(maxRow[i][j][lg], maxRow[i][j + (1 << lg) - 1][lg]);
  }

  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= m; j++)
      maxCol[i][j][0] = a[j][i];
    for (int lg = 0; lg < 9; lg++)
      for (int j = 1; j + (1 << lg + 1) - 1 <= m; j++)
        maxCol[i][j][lg + 1] = max(maxCol[i][j][lg], maxCol[i][j + (1 << lg) - 1][lg]);
  }

  for (int j = 0; j < 10; j++)
    for (int i = 1 << j; i < 1 << j + 1; i++)
      lg2[i] = j;
}

int getMax(int arr[777][11], int l, int r)
{
  int curLg2 = lg2[r - l + 1];
  return max(arr[l][curLg2], arr[r - (1 << curLg2) + 1][curLg2]);
}

void populateIntervals(int row, int l, int r)
{
  if (l >= r - 1)
    return;
  intervals.push_back({l, r});
  int id = l + 1;
  for (int i = l + 2; i < r; i++)
    if (a[row][i] > a[row][id])
      id = i;
  populateIntervals(row, l, id);
  populateIntervals(row, id, r);
}

long long subtask4()
{
  init();
  long long ans = 0;
  for (int i = 2; i < m; i++)
  {
    intervals.clear();
    populateIntervals(i, 1, n);
    int numIntervals = intervals.size();
    vector<int> isGoodInterval(numIntervals, 1);
    vector<int> isGoodCol(n + 1, 0);
    for (int ii = i; ii < m; ii++)
    {
      // check col
      for (int j = 2; j < n; j++)
        isGoodCol[j] = isGoodCol[j - 1] + (getMax(maxCol[j], i, ii) < min(a[i - 1][j], a[ii + 1][j]));
      // check row
      for (int j = 0; j < numIntervals; j++)
      {
        int l = intervals[j].first, r = intervals[j].second;
        int maxInterval = getMax(maxRow[ii], l + 1, r - 1);
        isGoodInterval[j] &= maxInterval < min(a[ii][l], a[ii][r]);
        ans += isGoodInterval[j] && isGoodCol[r - 1] - isGoodCol[l] == r - 1 - l;
      }
    }
  }
  return ans;
}

int calc(int l, int r)
{
  if (l >= r - 1)
    return 0;
  int id = l + 1;
  for (int i = l + 2; i < r; i++)
    if (a[2][i] > a[2][id])
      id = i;
  int isGoodInterval = a[2][id] < min(a[2][l], a[2][r]) && isGood[2][r - 1] - isGood[2][l] == r - 1 - l;
  return calc(l, id) + calc(id, r) + isGoodInterval;
}

long long subtask5()
{
  for (int i = 2; i < m; i++)
    for (int j = 2; j < n; j++)
      isGood[i][j] = isGood[i][j - 1] + (a[i][j] < min(a[i - 1][j], a[i + 1][j]));
  return calc(1, n);
}

int getSum(int x, int y, int xx, int yy)
{
  return sum[xx][yy] + sum[x][y] - sum[xx][y] - sum[x][yy];
}

long long subtask6()
{
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];

  vector<int> maxCol(n + 1, 0);
  long long ans = 0;
  for (int i = 2; i < m; i++)
  {
    int maxRow = 0;
    for (int j = 2; j < n; j++)
      if (!a[i][j])
      {
        maxRow++;
        maxCol[j]++;
        int ii = i - maxCol[j] + 1, jj = j - maxRow + 1;
        ans += getSum(ii - 1, jj - 1, i, j) == 0 &&
               getSum(ii - 2, jj - 1, ii - 1, j) == maxRow &&
               getSum(i, jj - 1, i + 1, j) == maxRow &&
               getSum(ii - 1, jj - 2, i, jj - 1) == maxCol[j] &&
               getSum(ii - 1, j, i, j + 1) == maxCol[j];
      }
      else maxRow = maxCol[j] = 0;
  }

  return ans;
}

long long count_rectangles(vector<vector<int>> _a)
{
  m = _a.size();
  n = _a[0].size();
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      a[i][j] = _a[i - 1][j - 1];

  if (m == 3)
    return subtask5();

  if (max(m, n) <= 700)
    return subtask4();

  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      if (a[i][j] > 1)
        return 0;

  return subtask6();
}

Compilation message (stderr)

rect.cpp: In function 'void init()':
rect.cpp:16:36: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
       for (int j = 1; j + (1 << lg + 1) - 1 <= n; j++)
                                 ~~~^~~
rect.cpp:25:36: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
       for (int j = 1; j + (1 << lg + 1) - 1 <= m; j++)
                                 ~~~^~~
rect.cpp:30:37: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
     for (int i = 1 << j; i < 1 << j + 1; i++)
                                   ~~^~~

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