Submission #872978

#	Time	Username	Problem	Language	Result	Execution time	Memory
872978		nguyentunglam	Rectangles (IOI19_rect)	C++17	49 / 100	1314 ms	104636 KiB

rect

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

const int N = 710;

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

bitset<N> row[N][N], col[N][N];

long long count_rectangles (vector<vector<int> > _a) {
  int 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;
      // cout << R[j] << " " << << endl;
      // if (j == 0) cout << st.top() << endl;
      st.push(j);
      // cout << st.top() << endl;
    }
    for(int j = 0; j < m; j++) row[L[j]][R[j]][i] = 1;
    // for(int j = m - 1; j >)
    // for(int j = 0; j < m; j++) cout << a[i][j] << " ";
    // for(int j = 0; j < m; j++) cout << L[j] << " " << R[j] << " " << i << endl;
    cout << endl;
  }

  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;
      // if (j == 2) cout << st.size() << endl;
      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++) col[L[i]][R[i]][j] = 1;
  }

  // cout << endl;

  int ans = 0;

  // cout << col[4][4][2] << endl;

  // cout << n - 2 << endl;

  for(int left = 1; left < m - 1; left++) {
    for(int up = 1; up < n - 1; up++) for(int down = up; down < n - 1; down++) if (col[up][down][left]) {
      // cout << up << " " << down << endl;
      for(int right = left; right < m - 1 && col[up][down][right]; right++) {
        bool ok = 1;
        for(int j = up; j <= down && ok; j++) ok &= row[left][right][j];
        if (ok) {
          ans++;
          // cout << up << " " << down << " " << left << " " << right << endl;
          // cout << left << " " << right << " " << up << " " << down << endl;
        }
      }
    }
  }

  // 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);
// }

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28