Submission #155687

#	Time	Username	Problem	Language	Result	Execution time	Memory
155687		flashmt	Rectangles (IOI19_rect)	C++17	72 / 100	5085 ms	195428 KiB

rect

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> stRow, stCol, lastRow, lastCol, cntRow, cntCol;

long long solve(vector<pair<int, int>> &rows, vector<pair<int, int>> &cols)
{
  long long res = 0;
  sort(rows.begin(), rows.end());
  sort(cols.begin(), cols.end());
  for (auto u : rows)
    for (auto v : cols)
      res += v.second >= u.second && u.first >= v.first;
  return res;
}

long long count_rectangles(vector<vector<int>> a)
{
  int m = a.size(), n = a[0].size();
  stRow = vector<vector<int>>(m, vector<int>(1, 0));
  stCol = vector<vector<int>>(n, vector<int>(1, 0));
  lastRow = vector<vector<int>>(m, vector<int>(m, -1));
  lastCol = vector<vector<int>>(n, vector<int>(n, -1));
  cntRow = vector<vector<int>>(m, vector<int>(m, 0));
  cntCol = vector<vector<int>>(n, vector<int>(n, 0));

  long long ans = 0;
  for (int i = 0; i < m - 1; i++)
    for (int j = 0; j < n - 1; j++)
    {
      // row
      int hasEqual = 0;
      vector<pair<int, int>> cols;
      while (!stRow[i].empty())
      {
        int k = stRow[i].back();
        if (!hasEqual)
        {
          if (lastCol[k][j + 1] + 1 == i) cntCol[k][j + 1]++;
          else cntCol[k][j + 1] = 1;
          lastCol[k][j + 1] = i;
          if (j > k)
            cols.push_back({j - k, cntCol[k][j + 1]});
        }
        if (a[i][j + 1] < a[i][k])
          break;
        if (a[i][j + 1] == a[i][k])
          hasEqual = 1;
        stRow[i].pop_back();
      }
      stRow[i].push_back(j + 1);

      // col
      hasEqual = 0;
      vector<pair<int, int>> rows;
      while (!stCol[j].empty())
      {
        int k = stCol[j].back();
        if (!hasEqual)
        {
          if (lastRow[k][i + 1] + 1 == j) cntRow[k][i + 1]++;
          else cntRow[k][i + 1] = 1;
          lastRow[k][i + 1] = j;
          if (i > k)
            rows.push_back({cntRow[k][i + 1], i - k});
        }
        if (a[i + 1][j] < a[k][j])
          break;
        if (a[i + 1][j] == a[k][j])
          hasEqual = 1;
        stCol[j].pop_back();
      }
      stCol[j].push_back(i + 1);

      ans += solve(rows, cols);
    }

  return ans;
}

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