oj.uz

Submission #844758

# Submission time Handle Problem Language Result Execution time Memory
844758 2023-09-05T19:59:18 Z qthang2k11 Rectangles (IOI19_rect) C++17
0 / 100
 41 ms 206016 KB 
// [+] 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.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 158556 KB Output is correct
2 Correct 34 ms 160768 KB Output is correct
3 Correct 33 ms 160616 KB Output is correct
4 Correct 33 ms 160604 KB Output is correct
5 Correct 33 ms 160616 KB Output is correct
6 Incorrect 33 ms 160596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 158556 KB Output is correct
2 Correct 34 ms 160768 KB Output is correct
3 Correct 33 ms 160616 KB Output is correct
4 Correct 33 ms 160604 KB Output is correct
5 Correct 33 ms 160616 KB Output is correct
6 Incorrect 33 ms 160596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 158556 KB Output is correct
2 Correct 34 ms 160768 KB Output is correct
3 Correct 33 ms 160616 KB Output is correct
4 Correct 33 ms 160604 KB Output is correct
5 Correct 33 ms 160616 KB Output is correct
6 Incorrect 33 ms 160596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 158556 KB Output is correct
2 Correct 34 ms 160768 KB Output is correct
3 Correct 33 ms 160616 KB Output is correct
4 Correct 33 ms 160604 KB Output is correct
5 Correct 33 ms 160616 KB Output is correct
6 Incorrect 33 ms 160596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 206016 KB Output is correct
2 Correct 41 ms 201804 KB Output is correct
3 Correct 40 ms 205660 KB Output is correct
4 Correct 33 ms 158552 KB Output is correct
5 Incorrect 41 ms 205908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 158556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 158556 KB Output is correct
2 Correct 34 ms 160768 KB Output is correct
3 Correct 33 ms 160616 KB Output is correct
4 Correct 33 ms 160604 KB Output is correct
5 Correct 33 ms 160616 KB Output is correct
6 Incorrect 33 ms 160596 KB Output isn't correct
7 Halted 0 ms 0 KB -