제출 #420824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420824		SSRS	Rectangles (IOI19_rect)	C++14	컴파일 에러	0 ms	0 KiB

rect

#include <bits/stdc++.h>
using namespace std;
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;
    int p = 32 - __builtin_clz(d);
    return max(B[p][L], B[p][R - (1 << d)]);
  }
};
long long count_rectangles(vector<vector<int>> a){
  int n = a.size();
  int m = a[0].size();
  assert(n <= 200 && m <= 200);
  vector<segment_tree> STh(n);
  for (int i = 0; i < n; i++){
    STh[i] = segment_tree(a[i]);
  }
  vector<segment_tree> 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] = segment_tree(b);
  }
  set<tuple<int, int, int, int>> st;
  for (int i = 1; i < n - 1; i++){
    for (int j = 1; j < m - 1; j++){
      int l = j;
      while (l > 0){
        if (a[i][l - 1] > a[i][j]){
          break;
        }
        l--;
      }
      int r = j + 1;
      while (r < m){
        if (a[i][r] > a[i][j]){
          break;
        }
        r++;
      }
      int u = i;
      while (u > 0){
        if (a[u - 1][j] > a[i][j]){
          break;
        }
        u--;
      }
      int d = i + 1;
      while (d < n){
        if (a[d][j] > a[i][j]){
          break;
        }
        d++;
      }
      if (l > 0 && r < m && u > 0 && d < n){
        if (st.count(make_tuple(l, r, u, d)) == 0){
          bool ok = true;
          for (int x = u; x < d; x++){
            if (STh[x].range_max(l, r) >= min(a[x][l - 1], a[x][r])){
              ok = false;
            }
          }
          for (int y = l; y < r; y++){
            if (STv[y].range_max(u, d) >= min(a[u - 1][y], a[d][y])){
              ok = false;
            }
          }
          if (ok){
            st.insert(make_tuple(l, r, u, d));
          }
        }
      }
    }
  }
  return st.size();
}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:32:10: error: 'segment_tree' was not declared in this scope
   32 |   vector<segment_tree> STh(n);
      |          ^~~~~~~~~~~~
rect.cpp:32:22: error: template argument 1 is invalid
   32 |   vector<segment_tree> STh(n);
      |                      ^
rect.cpp:32:22: error: template argument 2 is invalid
rect.cpp:34:8: error: invalid types 'int[int]' for array subscript
   34 |     STh[i] = segment_tree(a[i]);
      |        ^
rect.cpp:36:22: error: template argument 2 is invalid
   36 |   vector<segment_tree> STv(m);
      |                      ^
rect.cpp:42:8: error: invalid types 'int[int]' for array subscript
   42 |     STv[i] = segment_tree(b);
      |        ^
rect.cpp:79:20: error: invalid types 'int[int]' for array subscript
   79 |             if (STh[x].range_max(l, r) >= min(a[x][l - 1], a[x][r])){
      |                    ^
rect.cpp:84:20: error: invalid types 'int[int]' for array subscript
   84 |             if (STv[y].range_max(u, d) >= min(a[u - 1][y], a[d][y])){
      |                    ^