Submission #844763

#	Time	Username	Problem	Language	Result	Execution time	Memory
844763		qthang2k11	Rectangles (IOI19_rect)	C++17	100 / 100	1990 ms	564236 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], rh[N], lw[N], rw[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 = N - 1, 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[j] = j - 1;
      while (lw[j] > 0 && a[i][j] >= a[i][lw[j]])
        lw[j] = lw[lw[j]];
    }
    for (int j = n; j > 0; j--) {
      rw[j] = j + 1;
      while (rw[j] <= n && a[i][j] >= a[i][rw[j]])
        rw[j] = rw[rw[j]];
    }
    for (int j = 1; j <= n; j++) {
      int l = lw[j] + 1, r = rw[j] - 1;
      if (1 < l && l <= r && r < n && range[l][r].second != i) {
        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] = i - 1;
      while (lh[i] > 0 && a[i][j] >= a[lh[i]][j])
        lh[i] = lh[lh[i]];
    }
    for (int i = m; i > 0; i--) {
      rh[i] = i + 1;
      while (rh[i] <= m && a[i][j] >= a[rh[i]][j])
        rh[i] = rh[rh[i]];
    }
    for (int i = 1; i <= m; i++) {
      int l = lh[i] + 1, r = rh[i] - 1;
      if (1 < l && l <= r && r < m && range[l][r].second != j) {
        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: 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