Submission #844766

#	Time	Username	Problem	Language	Result	Execution time	Memory
844766		garyye	Rectangles (IOI19_rect)	C++17	100 / 100	2839 ms	542324 KiB

rect

#include "rect.h"

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

#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
typedef pair<int, int> i2;
typedef long long ll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;

const int N = 2505;
vector<int> C[N][N];
int L[N][N], R[N][N];
set<int> S[N];

long long count_rectangles(vvi A) {
  int n = SZ(A), m = SZ(A[0]);

  auto fun = [](vector<int> a) {
    vector<i2> ans;
    int s = SZ(a);
    vector<int> p(s), l(s, -1), r(s, -1);
    for (int i = 0; i < s; ++i) p[i] = i;
    sort(p.begin(), p.end(), [&](int i, int j) { return a[i] < a[j]; });
    for (int i : p) {
      i2 x = {i, i};
      if (i > 0 && l[i - 1] != -1) x.fi = l[i - 1];
      if (i + 1 < s && r[i + 1] != -1) x.se = r[i + 1];

      if (x.fi > 0 && x.se + 1 < s && min(a[x.fi - 1], a[x.se + 1]) > a[i]) {
        ans.push_back(x);
      }
      r[x.fi] = x.se;
      l[x.se] = x.fi;
    }

    return ans;
  };

  for (int j = 0; j < m; ++j) {
    vector<int> col(n);
    for (int i = 0; i < n; ++i) col[i] = A[i][j];
    auto pp = fun(col);

    for (auto& [i1, i2] : pp) {
      C[i2][j].push_back(i1);
    }
  }

  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    vector<int> p(m), l(m, -1), r(m, -1);
    for (int j = 0; j < m; ++j) p[j] = j, S[j].clear();
    sort(p.begin(), p.end(), [&](int l, int r) -> bool { return A[i][l] < A[i][r]; });

    for (int j : p) {
      i2 x = {j, j};

      set<int> cur(ALL(C[i][j]));
      set<int> del;

      auto inspect = [&](set<int>& s) {
        for (int c : cur)
          if (!s.count(c))
            del.insert(c);
      };

      if (j > 0 && l[j - 1] != -1) {
        x.fi = l[j - 1];
        inspect(S[x.fi]);
      }
      if (j + 1 < m && r[j + 1] != -1) {
        x.se = r[j + 1];
        inspect(S[l[x.se]]);
      }

      for (int x : del) cur.erase(x);

      if (x.fi > 0 && x.se + 1 < m && min(A[i][x.fi - 1], A[i][x.se + 1]) > A[i][j]) {
        if (i - R[x.fi][x.se] > 1) {
          L[x.fi][x.se] = i;
        }
        R[x.fi][x.se] = i;
        for (int i1 : cur) {
          if (i1 >= L[x.fi][x.se]) {
            ans++;
          }
        }
      }
      r[x.fi] = x.se;
      l[x.se] = x.fi;
      S[x.fi] = cur;
    }
  }
  return ans;
}

• 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: 28 / 28