Submission #873201

#	Time	Username	Problem	Language	Result	Execution time	Memory
873201		nguyentunglam	Rectangles (IOI19_rect)	C++17	100 / 100	2158 ms	401428 KiB

rect

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 2510;

int a[N][N], L[N], R[N], f[N][N], g[N][N];

int n, m;

vector<tuple<int, int, int> > row[N], col[N], query[N];

stack<int> S;

int bit[N];

void up (int pos, int val) {
  for(pos; pos; pos -= pos & -pos) {
    S.push(pos);
    bit[pos] += val;
  }
}

int get(int pos) {
  int ret = 0;
  for(pos; pos <= n; pos += pos & -pos) ret += bit[pos];
  return ret;
}

void rollback () {
  while (!S.empty()) bit[S.top()] = 0, S.pop();
}

long long count_rectangles (vector<vector<int> > _a) {
  n = _a.size(), m = _a[0].size();

  for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) a[i][j] = _a[i][j];

  for(int i = 1; i < n - 1; i++) {
    stack<int> st;
    for(int j = 0; j < m; j++) {
      while (!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
      L[j] = st.empty() ? 0 : st.top() + 1;
      st.push(j);
    }
    while (!st.empty()) st.pop();
    for(int j = m - 1; j >= 0; j--) {
      while (!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
      R[j] = st.empty() ? m : st.top() - 1;
      st.push(j);
    }
    for(int j = 0; j < m; j++) if (L[j] > 0 && R[j] < m - 1) row[i].emplace_back(L[j], R[j], 0);
    sort(all(row[i]));
    row[i].resize(unique(all(row[i])) - row[i].begin());
  }

  for(int i = 0; i < n; i++) row[i].emplace_back(1e9, 1e9, 1e9);

  for(int j = 1; j < m - 1; j++) {
    stack<int> st;
    for(int i = 0; i < n; i++) {
      while (!st.empty() && a[st.top()][j] <= a[i][j]) st.pop();
      L[i] = st.empty() ? 0 : st.top() + 1;
      st.push(i);
    } 
    while (!st.empty()) st.pop();
    for(int i = n - 1; i >= 0; i--) {
      while (!st.empty() && a[st.top()][j] <= a[i][j]) st.pop();
      R[i] = st.empty() ? n : st.top() - 1;
      st.push(i);
    }
    for(int i = 0; i < n; i++) if (L[i] > 0 && R[i] < n - 1) col[j].emplace_back(L[i], R[i], 0);
    sort(all(col[j]));
    col[j].resize(unique(all(col[j])) - col[j].begin());
  }

  for(int j = 0; j < m; j++) col[j].emplace_back(1e9, 1e9, 1e9);

  for(int j = m - 2; j >= 1; j--) {
    // cout << j << endl;
    for(auto &[l, r, f] : col[j]) if (l != 1e9) {
      auto &[_l, _r, _f] = *lower_bound(all(col[j + 1]), make_tuple(l, r, f));
      if (l == _l && r == _r) f = _f;
      else f = j;
      // cout << l << " " << r << " " << f << " " << j << endl;
      query[l].emplace_back(j, f, r);
    }
  }

  long long ans = 0;

  for(int i = n - 2; i >= 1; i--) {
    int k = 0;
    sort(all(query[i]));
    for(auto &[l, r, f] : row[i]) {
      auto &[_l, _r, _f] = *lower_bound(all(row[i + 1]), make_tuple(l, r, f));
      if (l == _l && r == _r) f = _f;
      else f = i;
    }
    int pre = 0;
    for(auto &[left, right, down] : query[i]) {
      if (pre != left) rollback();
      while (k < row[i].size()) {
        auto &[l, r, f] = row[i][k];
        if (l < left) {
          rollback();
          k++;
          continue;
        }
        if (l > left) break;
        if (r > right) break;
        pre = l;
        // cout << l << " " << r << " " << f << endl;
        up(f, 1);
        k++;
      }
      if (pre != left) rollback();
      ans += get(down);
      // cout << get(down) << " " << i << " " << left << " " << right << endl;
    }
    rollback();
  }

  // cout << ans;

  return ans;
}

// int32_t main() {
//   #define task ""

//   cin.tie(0) -> sync_with_stdio(0);

//   if (fopen("task.inp", "r")) {
//     freopen("task.inp", "r", stdin);
//     freopen("task.out", "w", stdout);
//   }

//   if (fopen(task".inp", "r")) {
//     freopen (task".inp", "r", stdin);
//     freopen (task".out", "w", stdout);
//   }

//   int n, m; cin >> n >> m;

//   vector<vector<int> > _tmp;

//   for(int i = 0; i < n; i++) {
//     vector<int> tmp;
//     for(int j = 0; j < m; j++) {
//       int x; cin >> x;
//       tmp.push_back(x);
//     }
//     _tmp.push_back(tmp);
//   }

//   count_rectangles(_tmp);
// }

Compilation message (stderr)

rect.cpp: In function 'void up(int, int)':
rect.cpp:19:7: warning: statement has no effect [-Wunused-value]
   19 |   for(pos; pos; pos -= pos & -pos) {
      |       ^~~
rect.cpp: In function 'int get(int)':
rect.cpp:27:7: warning: statement has no effect [-Wunused-value]
   27 |   for(pos; pos <= n; pos += pos & -pos) ret += bit[pos];
      |       ^~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:104:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |       while (k < row[i].size()) {
      |              ~~^~~~~~~~~~~~~~~

• 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