Submission #1069764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069764		TAhmed33	Rectangles (IOI19_rect)	C++17	100 / 100	2612 ms	995456 KiB

rect

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize ("Ofast")
const int B = 3000;
struct BIT {
  int tree[B];
  void add (int x, int y) {
    for (; x < B; x += x & (-x)) {
      tree[x] += y;
    }
  }
  int get (int x) {
    int sum = 0;
    for (; x > 0; x -= x & (-x)) {
      sum += tree[x];
    }
    return sum;
  }
 
} cur;
vector <int> ii[2501][2501], jj[2501][2501];
vector <pair <int, int>> gg[2501][2501], hh[2501][2501];
int last[2501][2501], dd[2501][2501];
ll count_rectangles (vector <vector <int>> a) {
  int n = a.size(), m = a[0].size();
  for (int i = 0; i < n; i++) {
    stack <int> cur;
    cur.push(0);
    for (int j = 1; j < m; j++) {
      while (!cur.empty() && a[i][j] > a[i][cur.top()]) {
        cur.pop();
      }
      if (!cur.empty() && cur.top() + 1 <= j - 1) {
        ii[i][j - 1].push_back(cur.top() + 1);
      }
      cur.push(j);
    }
    while (!cur.empty()) {
      cur.pop();
    }
    cur.push(m - 1);
    for (int j = m - 2; j >= 0; j--) {
      while (!cur.empty() && a[i][j] > a[i][cur.top()]) {
        cur.pop();
      }
      if (!cur.empty() && j + 1 <= cur.top() - 1 && a[i][j] != a[i][cur.top()]) {
        ii[i][cur.top() - 1].push_back(j + 1);
      }
      cur.push(j);
    }
  }
  for (int i = 0; i < m; i++) {
    stack <int> cur;
    cur.push(0);
    for (int j = 1; j < n; j++) {
      while (!cur.empty() && a[j][i] > a[cur.top()][i]) {
        cur.pop();
      }
      if (!cur.empty() && cur.top() + 1 <= j - 1) {
        jj[j - 1][i].push_back(cur.top() + 1);
      }
      cur.push(j);
    }
    while (!cur.empty()) {
      cur.pop();
    }
    cur.push(n - 1);
    for (int j = n - 2; j >= 0; j--) {
      while (!cur.empty() && a[j][i] > a[cur.top()][i]) {
        cur.pop();
      }
      if (!cur.empty() && j + 1 <= cur.top() - 1 && a[j][i] != a[cur.top()][i]) {
        jj[cur.top() - 1][i].push_back(j + 1);
      }
      cur.push(j);
    }
  }
  for (int i = 0; i < n; i++) {
  	for (int j = 0; j < m; j++) {
  		last[i][j] = dd[i][j] = 0;
  	}
  }
  for (int i = 1; i + 1 < n; i++) {
    for (int j = 1; j + 1 < m; j++) {
      for (auto k : ii[i][j]) {
        if (last[k][j] == i - 1) {
          dd[k][j]++;
        } else {
          dd[k][j] = 1;
        }
        gg[i][j].push_back({j - k + 1, dd[k][j]});
        last[k][j] = i;
      }
      ii[i][j].clear(); ii[i][j].shrink_to_fit();
    }
  }
  for (int i = 0; i < n; i++) {
  	for (int j = 0; j < m; j++) {
  		last[i][j] = dd[i][j] = 0;
  	}
  }
  for (int j = 1; j + 1 < m; j++) {
    for (int i = 1; i + 1 < n; i++) {
      for (auto k : jj[i][j]) {
        if (last[k][i] == j - 1) {
          dd[k][i]++;
        } else {
          dd[k][i] = 1;
        }
        hh[i][j].push_back({i - k + 1, dd[k][i]});
        last[k][i] = j;
      }
      jj[i][j].clear(); jj[i][j].shrink_to_fit();
    }
  }
  ll ans = 0;
  for (int i = 1; i + 1 < n; i++) {
    for (int j = 1; j + 1 < m; j++) {
      sort(gg[i][j].begin(), gg[i][j].end(), [&] (pair <int, int> x, pair <int, int> y) {
        return x.second < y.second;
      });
      sort(hh[i][j].begin(), hh[i][j].end());
      reverse(hh[i][j].begin(), hh[i][j].end());
      int ptr = 0;
      vector <int> d;
      for (auto a : gg[i][j]) {
        while (!hh[i][j].empty() && hh[i][j].back().first <= a.second) {
          cur.add(hh[i][j].back().second, 1);
          d.push_back(hh[i][j].back().second);
          hh[i][j].pop_back();
        }
        ans += cur.get(B - 1) - cur.get(a.first - 1);
      }
      for (auto j : d) {
        cur.add(j, -1);
      }
    }
  }
  return ans;
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:125:11: warning: unused variable 'ptr' [-Wunused-variable]
  125 |       int ptr = 0;
      |           ^~~

• 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