Submission #960644

#	Time	Username	Problem	Language	Result	Execution time	Memory
960644		AkibAzmain	Rectangles (IOI19_rect)	C++17	13 / 100	320 ms	61948 KiB

rect

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

long long count_rectangles (std::vector<std::vector<int> > a) {
  ll n = a.size ();
  ll m = a[0].size ();
  int c = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      if (a[i][j] == 0)
        {
          int k = i, l = j;
          while (k + 1 < n && a[k + 1][j] == 0) ++k;
          while (l + 1 < m && a[i][l + 1] == 0) ++l;
          bool y = 0 < i && k < n - 1 && 0 < j && l < m - 1;
          for (int ii = i + 1; y && ii <= k; ++ii)
            for (int jj = j + 1; y && jj <= l; ++jj)
              if (a[ii][jj]) y = false;
          for (int ii = i; y && ii <= k; ++ii)
            if (a[ii][j - 1] == 0 || a[ii][l + 1] == 0)
              y = false;
          for (int ii = j; y && ii <= l; ++ii)
            if (a[i - 1][ii] == 0 || a[k + 1][ii] == 0)
              y = false;
          if (y) ++c;
          queue < pair < int, int > > q;
          q.push ({ i, j });
          while (q.size ())
            {
              auto [x, y] = q.front ();
              q.pop ();
              if (x < 0 || x >= n || y < 0 || y >= m || a[x][y]) continue;
              a[x][y] = 1;
              q.push ({ x - 1, y });
              q.push ({ x + 1, y });
              q.push ({ x, y - 1 });
              q.push ({ x, y + 1 });
            }
        }
  return c;
  // vector < vector < vector < ll > > >
  //   ra (n, vector < vector < ll > > (m, vector < ll > (m))),
  //   ca (m, vector < vector < ll > > (n, vector < ll > (n)));
  // for (ll k = 0; k < n; ++k)
  //   for (ll i = 0; i < m; ++i)
  //     {
  //       int mx = 0;
  //       for (ll j = i + 2; j < m; ++j)
  //         {
  //           mx = max (mx, a[k][j - 1]);
  //           if (mx < a[k][i] && mx < a[k][j]) ra[k][i + 1][j - 1] = 1;
  //         }
  //     }
  // for (ll k = 0; k < m; ++k)
  //   for (ll i = 0; i < n; ++i)
  //     {
  //       int mx = 0;
  //       for (ll j = i + 2; j < n; ++j)
  //         {
  //           mx = max (mx, a[j - 1][k]);
  //           if (mx < a[i][k] && mx < a[j][k]) ca[k][i + 1][j - 1] = 1;
  //         }
  //     }
  // for (ll i = 1; i < n; ++i)
  //   for (ll j = 0; j < m; ++j)
  //     for (ll k = 0; k < m; ++k)
  //       ra[i][j][k] += ra[i - 1][j][k];
  // for (ll i = 1; i < m; ++i)
  //   for (ll j = 0; j < n; ++j)
  //     for (ll k = 0; k < n; ++k)
  //       ca[i][j][k] += ca[i - 1][j][k];
  // auto alp = [&] (auto &x, int a, int b, int c, int d)
  // {
  //   return (x[d][a][b] - (c ? x[c - 1][a][b] : 0)) == d - c + 1;
  // };
  // int c = 0;
  // for (ll i1 = 0; i1 < n; ++i1)
  //   for (ll i2 = i1; i2 < n; ++i2)
  //     for (ll j1 = 0; j1 < m; ++j1)
  //       for (ll j2 = j1; j2 < m; ++j2)
  //         if (alp (ca, i1, i2, j1, j2) && alp (ra, j1, j2, i1, i2))
  //           ++c;
  // return c;
}

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