제출 #155689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
155689		flashmt	Rectangles (IOI19_rect)	C++17	100 / 100	2037 ms	273396 KiB

rect

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

vector<vector<int>> stRow, stCol, lastRow, lastCol, cntRow, cntCol;
int tree[2525];

void add(int x, int v)
{
  for (int i = x; i <= 2500; i += i & -i)
    tree[i] += v;
}

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

int solve(vector<pair<int, int>> &rows, vector<pair<int, int>> &cols)
{
  int res = 0, i = 0;
  sort(rows.begin(), rows.end());
  for (auto u : rows)
  {
    while (i < cols.size() && cols[i].first <= u.first)
      add(cols[i++].second, 1);
    res += i - get(u.second - 1);
  }
  for (int j = 0; j < i; j++)
    add(cols[j].second, -1);
  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;
}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'int solve(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
rect.cpp:27:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (i < cols.size() && cols[i].first <= u.first)
            ~~^~~~~~~~~~~~~

• 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: 28 / 28