Submission #420793

#	Time	Username	Problem	Language	Result	Execution time	Memory
420793		SSRS	Rectangles (IOI19_rect)	C++14	0 / 100	2 ms	460 KiB

rect

#include <bits/stdc++.h>
using namespace std;
const int INF = 100000000;
struct segment_tree{
  int N;
  vector<int> ST;
  segment_tree(){
  }
  segment_tree(vector<int> A){
    int N2 = A.size();
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST = vector<int>(N * 2 - 1, INF);
    for (int i = 0; i < N2; i++){
      ST[N - 1 + i] = A[i];
    }
    for (int i = N - 2; i >= 0; i--){
      ST[i] = min(ST[i * 2 + 1], ST[i * 2 + 2]);
    }
  }
  int range_min(int L, int R, int i, int l, int r){
    if (r <= L || R <= l){
      return INF;
    } else if (L <= l && r <= R){
      return ST[i];
    } else {
      int m = (l + r) / 2;
      return min(range_min(L, R, i * 2 + 1, l, m), range_min(L, R, i * 2 + 2, m, r));
    }
  }
  int range_min(int L, int R){
    return range_min(L, R, 0, 0, N);
  }
};
long long count_rectangles(vector<vector<int>> a){
  int n = a.size();
  int m = a[0].size();
  assert(n <= 700 && m <= 700);
  vector<segment_tree> STh(n);
  for (int i = 0; i < n; i++){
    STh[i] = segment_tree(a[i]);
  }
  vector<segment_tree> STv(n);
  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){
        bool ok = true;
        for (int x = u; x < d; x++){
          if (STh[x].range_min(l, r) >= max(a[x][l - 1], a[x][r])){
            ok = false;
          }
        }
        for (int y = l; y < r; y++){
          if (STv[y].range_min(u, d) >= max(a[u - 1][y], a[d][y])){
            ok = false;
          }
        }
        if (ok){
          st.insert(make_tuple(l, r, u, d));
        }
      }
    }
  }
  return st.size();
}

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