Submission #441981

#	Time	Username	Problem	Language	Result	Execution time	Memory
441981		peijar	Rectangles (IOI19_rect)	C++17	10 / 100	5113 ms	557172 KiB

rect

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

template <class T> class Fenwick {
public:
  int lim;
  vector<T> bit;

  Fenwick(int n) : lim(n + 1), bit(lim) {}

  void upd(int pos, T val) {
    for (pos++; pos < lim; pos += pos & -pos)
      bit[pos] += val;
  }

  T sum(int r) { // < r
    T ret = 0;
    for (; r; r -= r & -r)
      ret += bit[r];
    return ret;
  }

  T sum(int l, int r) { // [l, r)
    return sum(r) - sum(l);
  }
};

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<pair<int, int>> columns[MAXN][MAXN], lines[MAXN][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;
    }

  for (int iLig = 0; iLig < nbLig; ++iLig)
    for (auto [fst, snd, len] : pairsLig[iLig])
      lines[iLig][fst].emplace_back(snd - fst + 1, len);
  for (int iCol = 0; iCol < nbCol; ++iCol)
    for (auto [fst, snd, len] : pairsCol[iCol])
      columns[fst][iCol].emplace_back(snd - fst + 1, 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 (int iCol = 0; iCol < nbCol; ++iCol) {
      Fenwick<int> fen(MAXN + 1);
      sort(columns[iLig][iCol].begin(), columns[iLig][iCol].end());
      sort(lines[iLig][iCol].begin(), lines[iLig][iCol].end());
      int curCol = (int)columns[iLig][iCol].size() - 1;
      for (int idLig = (int)lines[iLig][iCol].size() - 1; idLig >= 0; --idLig) {
        while (curCol >= 0 and columns[iLig][iCol][curCol].second >=
                                   lines[iLig][iCol][idLig].first)
          fen.upd(columns[iLig][iCol][curCol--].first, 1);
        sol += fen.sum(1 + lines[iLig][iCol][idLig].second);
      }

      /*for (auto [a, b] : lines[iLig][iCol])
        for (auto [c, d] : columns[iLig][iCol])
          sol += a <= d and c <= b;*/
    }
  /*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: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28