Submission #441978

#	Time	Username	Problem	Language	Result	Execution time	Memory
441978		peijar	Rectangles (IOI19_rect)	C++17	72 / 100	5042 ms	237640 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, 0}) -
               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, 0}) -
               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();

  int sol = 0;
  for (int iLig = 0; iLig < nbLig; ++iLig)
    for (auto [fstLig, sndLig, lenLig] : pairsLig[iLig]) {
      int id = lower_bound(pairsCol[fstLig].begin(), pairsCol[fstLig].end(),
                           goodPair{iLig, 0, 0}) -
               pairsCol[fstLig].begin();
      for (; id < (int)pairsCol[fstLig].size() and
             pairsCol[fstLig][id].fst == iLig;
           ++id) {
        auto [fstCol, sndCol, lenCol] = pairsCol[fstLig][id];
        if (lenLig >= sndCol - fstCol + 1 and lenCol >= sndLig - fstLig + 1)
          sol++;
      }
    }
  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