Submission #155522

#	Time	Username	Problem	Language	Result	Execution time	Memory
155522		flashmt	Rectangles (IOI19_rect)	C++17	0 / 100	206 ms	189944 KiB

rect

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

int m, n, a[N][N];
int l[N][N], r[N][N], u[N][N], d[N][N];
int treeRow[N][N], treeCol[N][N];
vector<pair<int, int>> id[A + 5];

void addTree(int tree[], int x)
{
  for (int i = x; i < N; i += i & -i)
    tree[i]++;
}

int getTree(int tree[], int x)
{
  int res = 0;
  for (int i = x; i; i -= i & -i)
    res += tree[i];
  return res;
}

void add(int x, int y)
{
  addTree(treeRow[x], y);
  addTree(treeCol[y], x);
  l[x][r[x][y]] = l[x][y];
  r[x][l[x][y]] = r[x][y];
  u[d[x][y]][y] = u[x][y];
  d[u[x][y]][y] = d[x][y];
}

int isEmpty(int tree[], int from, int to)
{
  return getTree(tree, to) == getTree(tree, from - 1);
}

int isFull(int tree[], int from, int to)
{
  return getTree(tree, to) - getTree(tree, from - 1) == to - from + 1;
}

int isRect(int x, int y)
{
  int curL = l[x][y] + 1, curR = r[x][y] - 1, curU = u[x][y] + 1, curD = d[x][y] - 1;
  if (curL < 2 || curU < 2 || curR > n - 1 || curL > m - 1)
    return 0;
  if (a[x][y] >= min({a[x][curL - 1], a[x][curR + 1], a[curU - 1][y], a[curD + 1][y]}))
    return 0;
  if (!isFull(treeRow[curU], curL, curR) || !isFull(treeRow[curD], curL, curR))
    return 0;
  if (!isFull(treeCol[curL], curU, curD) || !isFull(treeCol[curR], curU, curD))
    return 0;
  return 1;
}

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++)
    {
      id[_a[i - 1][j - 1]].push_back({i, j});
      a[i][j] = _a[i - 1][j - 1];
      u[i][j] = i - 1;
      d[i][j] = i + 1;
      l[i][j] = j - 1;
      r[i][j] = j + 1;
    }

  long long ans = 0;
  for (int v = 0; v <= A; v++)
    if (!id[v].empty())
    {
      for (auto u : id[v])
        add(u.first, u.second);
      for (auto u : id[v])
        ans += isRect(u.first, u.second);
    }
  return ans;
}

• 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