Submission #844758

#	Time	Username	Problem	Language	Result	Execution time	Memory
844758		qthang2k11	Rectangles (IOI19_rect)	C++17	0 / 100	41 ms	206016 KiB

rect

// [+] https://oj.uz/submission/286084
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 2505;

int lh[N][N], rh[N][N], lw[N][N], rw[N][N], a[N][N];
pair<int, int> range[N][N];

enum class EventType {
  add,
  get
};

struct Event {
  EventType type;
  int r, c;
  
  Event() = default;
  Event(EventType type, int r, int c):
    type(type), r(r), c(c) {}
  
  bool operator < (const Event &other) const {
    return tie(r, type) < tie(other.r, other.type);
  }
};

vector<Event> events[N][N];

struct FenwickTree {
  int BIT[N], n, all = 0;
  
  FenwickTree() = default;
  FenwickTree(int n): n(n) {}
  
  void update(int x, int w) {
    for (; x <= n; x += x & -x)
      BIT[x] += w;
    all += w;
  }
  
  int pref(int x) {
    int ans = 0;
    for (; x > 0; x -= x & -x)
      ans += BIT[x];
    return ans;
  }
  
  int suff(int x) {
    return all - pref(x - 1);
  }
} cnt;

ll count_rectangles(vector<vector<int>> b) {
  int m = b.size(), n = b[0].size();
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      a[i][j] = b[i - 1][j - 1];
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)
      range[i][j] = {-1, -1};
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      lw[i][j] = j - 1;
      while (lw[i][j] > 0 && a[i][j] >= a[i][lw[i][j]])
        lw[i][j] = lw[i][lw[i][j]];
    }
    for (int j = n; j > 0; j--) {
      rw[i][j] = j + 1;
      while (rw[i][j] <= n && a[i][j] >= a[i][rw[i][j]])
        rw[i][j] = rw[i][rw[i][j]];
    }
    for (int j = 1; j <= n; j++) {
      int l = lw[i][j] + 1, r = rw[i][j] - 1;
      if (1 < l && l <= r && r < n) {
        if (range[l][r].second == i - 1)
          range[l][r].second++;
        else range[l][r] = {i, i};
        int len = range[l][r].second - range[l][r].first + 1;
        events[i][r].emplace_back(EventType::get, len, r - l + 1);
      }
    }
  }
  for (int i = 1; i <= m; i++)
    for (int j = i; j <= m; j++)
      range[i][j] = {-1, -1};
  for (int j = 1; j <= n; j++) {
    for (int i = 1; i <= m; i++) {
      lh[i][j] = i - 1;
      while (lh[i][j] > 0 && a[i][j] >= a[lh[i][j]][j])
        lh[i][j] = lh[lh[i][j]][j];
    }
    for (int i = m; i > 0; i--) {
      rh[i][j] = i + 1;
      while (rh[i][j] <= m && a[i][j] >= a[rh[i][j]][j])
        rh[i][j] = rh[rh[i][j]][j];
    }
    for (int i = 1; i <= m; i++) {
      int l = lh[i][j] + 1, r = rh[i][j] - 1;
      if (1 < l && l <= r && r < m) {
        if (range[l][r].second == j - 1)
          range[l][r].second++;
        else range[l][r] = {j, j};
        int len = range[l][r].second - range[l][r].first + 1;
        events[r][j].emplace_back(EventType::add, r - l + 1, len);
      }
    }
  }
  ll ans = 0;
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      auto &events = ::events[i][j];
      sort(events.begin(), events.end());
      for (const auto &event: events) {
        if (event.type == EventType::add) {
          cnt.update(event.c, +1);
        } else {
          ans += cnt.suff(event.c);
        }
      }
      for (const auto &event: events) 
        if (event.type == EventType::add) 
          cnt.update(event.c, -1);
    }
  }
	return ans;
}

#ifdef LOCAL
int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	for (int i = 0; i < n; i++)	{
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}

	long long result = count_rectangles(a);

  cout << result;
	return 0;
}
#endif

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