Submission #795456

#	Time	Username	Problem	Language	Result	Execution time	Memory
795456		WLZ	Rectangles (IOI19_rect)	C++17	59 / 100	5076 ms	37524 KiB

rect

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

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;

long long count_rectangles(std::vector<std::vector<int> > a) {
  int n = (int) a.size(), m = (int) a[0].size();
  vector<vii> segs(n);
  for (int i = 1; i < n - 1; i++) {
    for (int j = 0; j < m - 2; j++) {
      int mx = -1;
      for (int k = j + 1; k < m - 1; k++) {
        mx = max(mx, a[i][k]);
        if (min(a[i][j], a[i][k + 1]) > mx) segs[i].emplace_back(j, k + 1);
      }
    }
  }
  int seg_cnt[m][m];
  ll ans = 0;
  for (int r1 = 0; r1 < n - 2; r1++) {
    vector<int> vert_mx(m, -1);
    memset(seg_cnt, 0, sizeof seg_cnt);
    for (int r2 = r1 + 2; r2 < n; r2++) {
      for (int c = 0; c < m; c++) vert_mx[c] = max(vert_mx[c], a[r2 - 1][c]);
      vector<int> pre(m, 0);
      for (int c = 1; c < m - 1; c++) {
        if (min(a[r1][c], a[r2][c]) > vert_mx[c]) pre[c] = 1;
        pre[c] += pre[c - 1];
      }
      pre[m - 1] = pre[m - 2];
      for (auto &[l, r] : segs[r2 - 1]) {
        if (++seg_cnt[l][r] == r2 - r1 - 1 && pre[r - 1] - pre[l] == r - l - 1) {
          //cerr << r1 << ' ' << r2 << ' ' << l << ' ' << r << endl;
          ans++;
        }
      }
    }
  }
	return ans;
}

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