Submission #1126788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126788		VinhLuu	Rectangles (IOI19_rect)	C++20	100 / 100	1621 ms	506380 KiB

rect

#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;

//#define lpv

#ifndef lpv
#include "rect.h"
#endif // lpv

const int N = 3e3 + 5;
const int oo = 1e8;

int n, m, a[N][N], f[2][N << 1][N];
ll ans;

vector<int> col[N][N];

int get(int t,int l,int r,int x) {
  r++;
  int ret = oo;
  for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2) {
    if(l & 1) ret = min(ret, f[t][l ++][x]);
    if(r & 1) ret = min(ret, f[t][-- r][x]);
  }
  return ret;
}

long long count_rectangles(std::vector<std::vector<int>> _a) {
  n = _a.size();
  m = _a[0].size();
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= m; j ++) a[i][j] = _a[i - 1][j - 1];
  }

  for(int i = 1; i <= n; i ++) {
    stack<int> st;
    st.push(0);
    a[i][0] = oo;
    for(int j = 1; j <= m; j ++) {
      while(!st.empty() && a[i][st.top()] < a[i][j]) st.pop();
      int x = (st.top() == 0 ? 1 : st.top());
      f[0][i + n - 1][j] = j - x;
      st.push(j);
    }

    while(!st.empty()) st.pop();
    st.push(m + 1);
    a[i][m + 1] = oo;
    for(int j = m; j >= 1; j --) {
      while(!st.empty() && a[i][st.top()] < a[i][j]) st.pop();
      int x = (st.top() == m + 1 ? m : st.top());
//      if(i == 3 && j == 1) cerr << x << " " << x - j << " " <<  << " g\n";
      f[1][i + n - 1][j] = x - j;
      st.push(j);
    }
  }

  for(int j = 1; j <= m; j ++) {
    for(int i = n - 1; i >= 1; i --) for(int t = 0; t <= 1; t ++) {
      f[t][i][j] = min(f[t][i << 1][j], f[t][i << 1|1][j]);
    }
  }

  for(int j = 2; j < m; j ++) {
    stack<int> st;
    st.push(0);
    a[0][j] = oo;
    for(int i = 1; i <= n; i ++) {
      while(!st.empty() && a[st.top()][j] < a[i][j]) st.pop();
      int x = st.top();
      if(x && x != i - 1) col[i][x].push_back(j);
      st.push(i);
    }

    while(!st.empty()) st.pop();
    st.push(n + 1);
    a[n + 1][j] = oo;
    for(int i = n; i >= 1; i --) {
      while(!st.empty() && a[st.top()][j] < a[i][j]) st.pop();
      int x = st.top();

      if(x != n + 1 && x != i + 1) {
        col[x][i].push_back(j);
//        if(j == 4) cerr << x << " " << i << " " << j << " o\n";
      }
      st.push(i);
    }
  }

  for(int r = 1; r <= n; r ++) {


//    if(r != 3) continue;


    for(int l = r - 2; l >= 1; l --) if(!col[r][l].empty()) {
      sort(all(col[r][l])); col[r][l].resize(unique(all(col[r][l])) - col[r][l].begin());
//      cerr << r << " " << l << " t\n";
//      for(auto j : col[r][l]) cerr << j << " ";
//      cerr << "\n";
      int pre = -1, last = -1;
      for(auto i : col[r][l]) {
        if(pre == -1) pre = i;
        else if(i > last + 1) pre = i;
        last = i;
        int val = get(0, l + 1, r - 1, i + 1);
        int pos = i + 1 - val;
//        if(i == 4) cerr << l + 1 << " " << r - 1 << " " << i + 1 << " " << pos << " " << pre << " t\n";
        if(pos >= pre - 1 && pos != i) {
          int tmp = get(1, l + 1, r - 1, pos);
          if(pos + tmp >= i + 1) {
            ans++;
//            cerr << pos << " " << i + 1 << " " << l + 1 << " " << r - 1 << " x1\n";
          }
        }
      }
      pre = -1, last = -1;
      reverse(all(col[r][l]));
      for(auto i : col[r][l]) {
        if(pre == -1) pre = i;
        else if(i < last - 1) pre = i;
        last = i;
        int val = get(1, l + 1, r - 1, i - 1);
        int pos = i - 1 + val;
        if(pos <= pre + 1 && pos != i) {
          int tmp = get(0, l + 1, r - 1, pos);
          if(pos - tmp < i - 1) {
            ans++;
//            cerr << i - 1 << " " << pos << " " << l + 1 << " " << r - 1 << " h\n";
          }
        }
      }
//      cerr << l << " " << ans << " g\n";
    }
//    cerr << r << " " << ans << " f\n";
  }

  cerr << ans << "\n";

  return ans;
}

/*

6 6
2 13 15 14 12 15
17 6 8 3 10 2
6 18 16 20 13 12
4 4 4 20 19 13
5 12 12 2 10 17
9 9 3 17 9 19


6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6

*/


#ifdef lpv
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  int _n, _m;cin >> _n >> _m;
  vector<vector<int>> _a;
  for(int i = 1; i <= _n; i ++) {
    vector<int> tmp;
    for(int j = 1; j <= _m; j ++) {
      int x; cin >> x;
      tmp.push_back(x);
    }
    _a.push_back(tmp);
  }
  cout << count_rectangles(_a);
}
#endif // lpv

• 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