Submission #420878

#	Time	Username	Problem	Language	Result	Execution time	Memory
420878		SSRS	Rectangles (IOI19_rect)	C++14	50 / 100	801 ms	50372 KiB

rect

#include <bits/stdc++.h>
using namespace std;
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
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, 0);
    for (int i = 0; i < N2; i++){
      ST[N - 1 + i] = A[i];
    }
    for (int i = N - 2; i >= 0; i--){
      ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]);
    }
  }
  int range_max(int L, int R, int i, int l, int r){
    if (r <= L || R <= l){
      return 0;
    } else if (L <= l && r <= R){
      return ST[i];
    } else {
      int m = (l + r) / 2;
      return max(range_max(L, R, i * 2 + 1, l, m), range_max(L, R, i * 2 + 2, m, r));
    }
  }
  int range_max(int L, int R){
    return range_max(L, R, 0, 0, N);
  }
};
long long count_rectangles(vector<vector<int>> a){
  int n = a.size();
  int m = a[0].size();
  if (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();
  } else if (n < 3){
    return 0;
  } else if (n == 3){
    vector<bool> c(m);
    for (int i = 0; i < m; i++){
      c[i] = a[0][i] > a[1][i] && a[2][i] > a[1][i];
    }
    vector<int> S(m + 1);
    S[0] = 0;
    for (int i = 0; i < m; i++){
      S[i + 1] = S[i];
      if (!c[i]){
        S[i + 1]++;
      }
    }
    map<int, vector<int>> mp;
    for (int j = 0; j < m; j++){
      mp[a[1][j]].push_back(j);
    }
    set<int> st = {-1, m};
    set<pair<int, int>> ans;
    for (auto itr = mp.rbegin(); itr != mp.rend(); itr++){
      vector<int> id = (*itr).second;
      for (int i : id){
        if (i > 0 && i < m - 1){
          int L = *prev(st.lower_bound(i)) + 1;
          int R = *st.lower_bound(i);
          if (0 < L && R < m){
            if (S[R] - S[L] == 0){
              ans.insert(make_pair(L, R));
            }
          }
        }
      }
      for (int i : id){
        st.insert(i);
      }  
    }
    return ans.size();
  } else {
    for (int i = 0; i < n; i++){
      for (int j = 0; j < m; j++){
        assert(a[i][j] <= 1);
      }
    }
    int ans = 0;
    vector<vector<bool>> used(n, vector<bool>(m, false));
    for (int i = 0; i < n; i++){
      for (int j = 0; j < m; j++){
        if (a[i][j] == 0 && !used[i][j]){
          used[i][j] = true;
          int u = i, d = i, l = j, r = j;
          int cnt = 0;
          queue<pair<int, int>> Q;
          Q.push(make_pair(i, j));
          bool ok = true;
          while (!Q.empty()){
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();
            u = min(u, x);
            d = max(d, x);
            l = min(l, y);
            r = max(r, y);
            cnt++;
            for (int k = 0; k < 4; k++){
              int x2 = x + dx[k];
              int y2 = y + dy[k];
              if (0 <= x2 && x2 < n && 0 <= y2 && y2 < m){
                if (a[x2][y2] == 0 && !used[x2][y2]){
                  used[x2][y2] = true;
                  Q.push(make_pair(x2, y2));
                }
              } else {
                ok = false;
              }
            }
          }
          if (ok){
            if (cnt == (d - u + 1) * (r - l + 1)){
              ans++;
            }
          }
        }
      }
    }
    return ans;
  }
}

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