Submission #441969

#	Time	Username	Problem	Language	Result	Execution time	Memory
441969		peijar	Rectangles (IOI19_rect)	C++17	72 / 100	5078 ms	284272 KiB

rect

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

const int MAXN = 2500;
int nbLig, nbCol;

struct goodPair {
  int fst, snd, len;
  goodPair(int l, int r) : fst(l), snd(r), len(1) {}
  goodPair(int l, int r, int le) : fst(l), snd(r), len(le) {}

  bool operator<(goodPair other) const {
    if (fst == other.fst)
      return snd < other.snd;
    return fst < other.fst;
  }
};

vector<goodPair> pairsLig[MAXN], pairsCol[MAXN];
vector<vector<signed>> height;

void precompute() {
  for (int iLig = 1; iLig < nbLig - 1; ++iLig) {
    vector<int> good;
    for (int iCol = 0; iCol < nbCol; ++iCol) {
      while (!good.empty() and height[iLig][good.back()] < height[iLig][iCol]) {
        if (good.back() + 1 < iCol)
          pairsLig[iLig].emplace_back(good.back() + 1, iCol - 1);
        good.pop_back();
      }
      if (!good.empty()) {
        if (good.back() + 1 < iCol)
          pairsLig[iLig].emplace_back(good.back() + 1, iCol - 1);
        if (height[iLig][good.back()] == height[iLig][iCol])
          good.pop_back();
      }
      good.push_back(iCol);
    }
    sort(pairsLig[iLig].begin(), pairsLig[iLig].end());
  }

  for (int iCol = 1; iCol < nbCol - 1; ++iCol) {
    vector<int> good;
    for (int iLig = 0; iLig < nbLig; ++iLig) {
      while (!good.empty() and height[good.back()][iCol] < height[iLig][iCol]) {
        if (good.back() + 1 < iLig)
          pairsCol[iCol].emplace_back(good.back() + 1, iLig - 1);
        good.pop_back();
      }
      if (!good.empty()) {
        if (good.back() + 1 < iLig)
          pairsCol[iCol].emplace_back(good.back() + 1, iLig - 1);
        if (height[good.back()][iCol] == height[iLig][iCol])
          good.pop_back();
      }
      good.push_back(iLig);
    }
    sort(pairsCol[iCol].begin(), pairsCol[iCol].end());
  }
  for (int iLig = nbLig - 2; iLig >= 0; --iLig)
    for (auto &[fst, snd, len] : pairsLig[iLig]) {
      int id = lower_bound(pairsLig[iLig + 1].begin(), pairsLig[iLig + 1].end(),
                           goodPair{fst, snd, len}) -
               pairsLig[iLig + 1].begin();
      if (id < (int)pairsLig[iLig + 1].size() and
          pairsLig[iLig + 1][id].fst == fst and
          pairsLig[iLig + 1][id].snd == snd)
        len = 1 + pairsLig[iLig + 1][id].len;
    }
  for (int iCol = nbCol - 2; iCol >= 0; --iCol)
    for (auto &[fst, snd, len] : pairsCol[iCol]) {
      int id = lower_bound(pairsCol[iCol + 1].begin(), pairsCol[iCol + 1].end(),
                           goodPair{fst, snd, len}) -
               pairsCol[iCol + 1].begin();
      if (id < (int)pairsCol[iCol + 1].size() and
          pairsCol[iCol + 1][id].fst == fst and
          pairsCol[iCol + 1][id].snd == snd)
        len = 1 + pairsCol[iCol + 1][id].len;
    }
}

long long count_rectangles(vector<vector<signed>> a) {
  height = a;
  nbLig = a.size(), nbCol = a[0].size();

  precompute();
  /*cout << "Lines : " << endl;
  for (int iLig = 0; iLig < nbLig; ++iLig) {
    cout << "====== Line " << iLig + 1 << " =======\n";
    for (auto [fst, snd, len] : pairsLig[iLig])
      cout << fst + 1 << ' ' << snd + 1 << ' ' << len << endl;
  }
  cout << "Columns : " << endl;
  for (int iCol = 0; iCol < nbCol; ++iCol) {
    cout << "===== Column " << iCol + 1 << " =========\n";
    for (auto [fst, snd, len] : pairsCol[iCol])
      cout << fst + 1 << ' ' << snd + 1 << ' ' << len << endl;
  }*/

  int sol = 0;
  for (int iLig = 0; iLig < nbLig; ++iLig)
    for (auto [fstLig, sndLig, lenLig] : pairsLig[iLig])
      for (auto [fstCol, sndCol, lenCol] : pairsCol[fstLig])
        if (fstCol == iLig and lenLig >= sndCol - fstCol + 1 and
            lenCol >= sndLig - fstLig + 1) {
          sol++;
          // cout << iLig + 1 << ' ' << fstLig + 1 << endl;
        }
  return sol;
}

• 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