Submission #420954

#	Time	Username	Problem	Language	Result	Execution time	Memory
420954		SSRS	Rectangles (IOI19_rect)	C++14	27 / 100	5081 ms	70004 KiB

rect

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
vector<int> C;
struct sparse_table{
  int LOG;
  vector<vector<int>> B;
  sparse_table(){
  }
  sparse_table(vector<int> A){
    int N = A.size();
    LOG = 32 - __builtin_clz(N);
    B = vector<vector<int>>(LOG, vector<int>(N, 0));
    for (int i = 0; i < N; i++){
      B[0][i] = A[i];
    }
    for (int i = 0; i < LOG - 1; i++){
      B[i + 1] = B[i];
      for (int j = 0; j < N - (1 << i); j++){
        B[i + 1][j] = max(B[i + 1][j], B[i][j + (1 << i)]);
      }
    }
  }
  int range_max(int L, int R){
    int d = R - L;
    return max(B[C[d]][L], B[C[d]][R - (1 << C[d])]);
  }
};
long long count_rectangles(vector<vector<int>> a){
  int n = a.size();
  int m = a[0].size();
  assert(n <= 700 && m <= 700);
  C = vector<int>(1000);
  for (int i = 1; i < 1000; i++){
    C[i] = 32 - __builtin_clz(i) - 1;
  }
  vector<vector<int>> L(n, vector<int>(m));
  vector<vector<int>> R(n, vector<int>(m));
  for (int i = 0; i < n; i++){
    map<int, vector<int>> mp;
    for (int j = 0; j < m; j++){
      mp[a[i][j]].push_back(j);
    }
    set<int> st = {-1, m};
    for (auto itr = mp.rbegin(); itr != mp.rend(); itr++){
      for (int x : (*itr).second){
        L[i][x] = *prev(st.lower_bound(x)) + 1;
        R[i][x] = *st.lower_bound(x);
      }
      for (int x : (*itr).second){
        st.insert(x);
      }
    }
  }
  vector<vector<int>> U(n, vector<int>(m));
  vector<vector<int>> D(n, vector<int>(m));
  for (int i = 0; i < m; i++){
    map<int, vector<int>> mp;
    for (int j = 0; j < n; j++){
      mp[a[j][i]].push_back(j);
    }
    set<int> st = {-1, n};
    for (auto itr = mp.rbegin(); itr != mp.rend(); itr++){
      for (int x : (*itr).second){
        U[x][i] = *prev(st.lower_bound(x)) + 1;
        D[x][i] = *st.lower_bound(x);
      }
      for (int x : (*itr).second){
        st.insert(x);
      }
    }
  }
  vector<sparse_table> STh(n);
  for (int i = 0; i < n; i++){
    STh[i] = sparse_table(a[i]);
  }
  vector<sparse_table> STv(m);
  for (int i = 0; i < m; i++){
    vector<int> b(n);
    for (int j = 0; j < n; j++){
      b[j] = a[j][i];
    }
    STv[i] = sparse_table(b);
  }
  set<tuple<int, int, int, int>> st;
  for (int i = 1; i < n - 1; i++){
    for (int j = 1; j < m - 1; j++){
      if (L[i][j] > 0 && R[i][j] < m && U[i][j] > 0 && D[i][j] < n){
        if (st.count(make_tuple(L[i][j], R[i][j], U[i][j], D[i][j])) == 0){
          bool ok = true;
          for (int x = U[i][j]; x < D[i][j]; x++){
            if (STh[x].range_max(L[i][j], R[i][j]) >= min(a[x][L[i][j] - 1], a[x][R[i][j]])){
              ok = false;
              break;
            }
          }
          if (ok){
            for (int y = L[i][j]; y < R[i][j]; y++){
              if (STv[y].range_max(U[i][j], D[i][j]) >= min(a[U[i][j] - 1][y], a[D[i][j]][y])){
                ok = false;
                break;
              }
            }
          }
          if (ok){
            st.insert(make_tuple(L[i][j], R[i][j], U[i][j], D[i][j]));
          }
        }
      }
    }
  }
  return st.size();
}

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