Submission #441641

#	Time	Username	Problem	Language	Result	Execution time	Memory
441641		peijar	Rectangles (IOI19_rect)	C++17	25 / 100	5079 ms	118144 KiB

rect

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

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

  vector<vector<int>> down(nbLig, vector<int>(nbCol));
  vector<vector<int>> up(nbLig, vector<int>(nbCol));
  vector<vector<int>> right(nbLig, vector<int>(nbCol));
  vector<vector<int>> left(nbLig, vector<int>(nbCol));

  for (int col = 0; col < nbCol; ++col) {
    for (int iLig = nbLig - 1; iLig >= 0; --iLig) {
      int nxt = iLig + 1;
      while (nxt < nbLig and a[iLig][col] > a[nxt][col])
        nxt = down[nxt][col];
      down[iLig][col] = nxt;
    }

    for (int iLig = 0; iLig < nbLig; ++iLig) {
      int nxt = iLig - 1;
      while (nxt >= 0 and a[iLig][col] > a[nxt][col])
        nxt = up[nxt][col];
      up[iLig][col] = nxt;
    }
  }

  for (int lig = 0; lig < nbLig; ++lig) {
    for (int iCol = nbCol - 1; iCol >= 0; --iCol) {
      int nxt = iCol + 1;
      while (nxt < nbCol and a[lig][iCol] > a[lig][nxt])
        nxt = right[lig][nxt];
      right[lig][iCol] = nxt;
    }
    for (int iCol = 0; iCol < nbCol; ++iCol) {
      int nxt = iCol - 1;
      while (nxt >= 0 and a[lig][iCol] > a[lig][nxt])
        nxt = left[lig][nxt];
      left[lig][iCol] = nxt;
    }
  }
  int sol = 0;
  for (int lig1 = 0; lig1 < nbLig; ++lig1)
    for (int lig2 = lig1 + 2; lig2 < nbLig; ++lig2)
      for (int col1 = 0; col1 < nbCol; ++col1)
        for (int col2 = col1 + 2; col2 < nbCol; ++col2) {
          bool ok = true;
          for (int i = lig1 + 1; i < lig2; ++i)
            ok &= right[i][col1] >= col2 and left[i][col2] <= col1;
          for (int i = col1 + 1; i < col2; ++i)
            ok &= up[lig2][i] <= lig1 and down[lig1][i] >= lig2;
          sol += ok;
        }

  return sol;
}

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