Submission #441810

#	Time	Username	Problem	Language	Result	Execution time	Memory
441810		peijar	Rectangles (IOI19_rect)	C++17	50 / 100	5061 ms	342612 KiB

rect

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

const int MAXN = 2500;
bool seen[2500][2500];
int DX[] = {-1, 1, 0, 0};
int DY[] = {0, 0, -1, 1};
int nbLig, nbCol;
int maxLig, minLig, minCol, maxCol, nbVus;
int available[MAXN][MAXN];
int ptr[MAXN];
int stk;
int toRemove[MAXN * MAXN];
vector<vector<signed>> val;

template <class T> class Fenwick {
public:
  int lim;
  vector<T> bit;

  Fenwick(int n) : lim(n + 1), bit(lim) {}

  void upd(int pos, T v) {
    for (pos++; pos < lim; pos += pos & -pos)
      bit[pos] += v;
  }

  T sum(int r) { // < r
    T ret = 0;
    for (; r; r -= r & -r)
      ret += bit[r];
    return ret;
  }

  T sum(int l, int r) { // [l, r)
    return sum(r) - sum(l);
  }
};

struct maxSeg {
  vector<int> seg;
  int deb;

  maxSeg(int n) {
    int p = 0;
    while ((1 << p) < n)
      ++p;
    deb = (1 << p);
    seg.resize(2 * deb + 1);
  }

  void upd(int i, int v) {
    i += deb;
    seg[i] = v;
    while (i > 1) {
      i /= 2;
      seg[i] = max(seg[2 * i], seg[2 * i + 1]);
    }
  }

  int query(int l, int r) {
    l += deb, r += deb;
    int ret = 0;
    while (l < r) {
      if (l % 2)
        ret = max(ret, seg[l]);
      if (r % 2 == 0)
        ret = max(ret, seg[r]);
      l = (l + 1) / 2;
      r = (r - 1) / 2;
    }
    if (l == r)
      ret = max(ret, seg[l]);
    return ret;
  }
};
struct minSeg {
  vector<int> seg;
  int deb;

  minSeg(int n) {
    int p = 0;
    while ((1 << p) < n)
      ++p;
    deb = (1 << p);
    seg.assign(2 * deb + 1, 1e18);
  }

  void upd(int i, int v) {
    i += deb;
    seg[i] = v;
    while (i > 1) {
      i /= 2;
      seg[i] = min(seg[2 * i], seg[2 * i + 1]);
    }
  }

  int query(int l, int r) {
    l += deb, r += deb;
    int ret = 1e18;
    while (l < r) {
      if (l % 2)
        ret = min(ret, seg[l]);
      if (r % 2 == 0)
        ret = min(ret, seg[r]);
      l = (l + 1) / 2;
      r = (r - 1) / 2;
    }
    if (l == r)
      ret = min(ret, seg[l]);
    return ret;
  }
};

void dfs(int iLig, int iCol) {
  if (nbLig <= iLig or iLig < 0 or iCol < 0 or iCol >= nbCol or
      seen[iLig][iCol] or val[iLig][iCol])
    return;
  nbVus++;
  maxLig = max(maxLig, iLig);
  minLig = min(minLig, iLig);
  minCol = min(minCol, iCol);
  maxCol = max(maxCol, iCol);
  seen[iLig][iCol] = true;
  for (int d = 0; d < 4; ++d) {
    int col = iCol + DX[d];
    int lig = iLig + DY[d];
    dfs(lig, col);
  }
}

int solveBinary() {
  int ret = 0;

  for (int iLig = 0; iLig < nbLig; ++iLig)
    for (int iCol = 0; iCol < nbCol; ++iCol)
      if (!seen[iLig][iCol] and !val[iLig][iCol]) {
        minLig = maxLig = iLig;
        minCol = maxCol = iCol;
        nbVus = 0;
        dfs(iLig, iCol);
        ret += nbVus == (maxLig - minLig + 1) * (maxCol - minCol + 1) and
               maxLig < nbLig - 1 and minLig > 0 and minCol > 0 and
               maxCol < nbCol - 1;
      }
  return ret;
}

long long count_rectangles(vector<vector<signed>> a) {
  val = a;
  nbLig = a.size(), nbCol = a[0].size();
  bool isBinary = true;
  for (auto v : a)
    for (auto w : v)
      isBinary &= w < 2;
  if (isBinary)
    return solveBinary();
  vector<vector<int>> down(nbLig, vector<int>(nbCol));
  vector<vector<int>> up(nbLig, vector<int>(nbCol));
  vector<vector<int>> right(nbLig, vector<int>(nbCol));
  vector<vector<int>> left(nbLig, vector<int>(nbCol));

  for (int col = 0; col < nbCol; ++col) {
    for (int iLig = nbLig - 1; iLig >= 0; --iLig) {
      int nxt = iLig + 1;
      while (nxt < nbLig and a[iLig][col] > a[nxt][col])
        nxt = down[nxt][col];
      down[iLig][col] = nxt;
    }

    for (int iLig = 0; iLig < nbLig; ++iLig) {
      int nxt = iLig - 1;
      while (nxt >= 0 and a[iLig][col] > a[nxt][col])
        nxt = up[nxt][col];
      up[iLig][col] = nxt;
    }
  }

  for (int lig = 0; lig < nbLig; ++lig) {
    for (int iCol = nbCol - 1; iCol >= 0; --iCol) {
      int nxt = iCol + 1;
      while (nxt < nbCol and a[lig][iCol] > a[lig][nxt])
        nxt = right[lig][nxt];
      right[lig][iCol] = nxt;
    }
    for (int iCol = 0; iCol < nbCol; ++iCol) {
      int nxt = iCol - 1;
      while (nxt >= 0 and a[lig][iCol] > a[lig][nxt])
        nxt = left[lig][nxt];
      left[lig][iCol] = nxt;
    }
  }

  vector<minSeg> segRight(nbCol, minSeg(nbLig));
  vector<maxSeg> segLeft(nbCol, maxSeg(nbLig));
  for (int iLig = 0; iLig < nbLig; ++iLig)
    for (int iCol = 0; iCol < nbCol; ++iCol) {
      segRight[iCol].upd(iLig, right[iLig][iCol]);
      segLeft[iCol].upd(iLig, left[iLig][iCol]);
    }

  long long sol = 0;
  Fenwick<int> fen(nbCol);
  for (int lig1 = 0; lig1 < nbLig; ++lig1)
    for (int lig2 = lig1 + 2; lig2 < nbLig; ++lig2) {
      fen.bit.assign(fen.lim, 0);
      for (int col2 = 2; col2 < nbCol; ++col2) {
        int x = max(0LL, segLeft[col2].query(lig1 + 1, lig2 - 1));
        if (x < nbCol)
          available[x][ptr[x]++] = col2;
      }

      int col2 = 0;
      for (int col1 = 0; col1 < nbCol - 1; ++col1) {
        if (col2 <= col1)
          col2 = col1 + 1;
        while (col2 < nbCol and up[lig2][col2] <= lig1 and
               down[lig1][col2] >= lig2)
          ++col2;
        while (ptr[col1])
          fen.upd(available[col1][--ptr[col1]], 1);
        int bnd = min(nbCol - 1, segRight[col1].query(lig1 + 1, lig2 - 1));
        if (col1 + 2 <= min(bnd, col2))
          sol += fen.sum(col1 + 2, min(bnd, col2) + 1);
      }
    }

  return sol;
}

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