oj.uz

Submission #420878

# Submission time Handle Problem Language Result Execution time Memory
420878 2021-06-08T14:36:19 Z SSRS Rectangles (IOI19_rect) C++14
50 / 100
 801 ms 50372 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 36 ms 852 KB Output is correct
23 Correct 37 ms 800 KB Output is correct
24 Correct 36 ms 776 KB Output is correct
25 Correct 3 ms 460 KB Output is correct
26 Correct 5 ms 588 KB Output is correct
27 Correct 5 ms 588 KB Output is correct
28 Correct 7 ms 616 KB Output is correct
29 Correct 2 ms 460 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 36 ms 852 KB Output is correct
18 Correct 37 ms 800 KB Output is correct
19 Correct 36 ms 776 KB Output is correct
20 Correct 3 ms 460 KB Output is correct
21 Correct 5 ms 588 KB Output is correct
22 Correct 5 ms 588 KB Output is correct
23 Correct 7 ms 616 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 0 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 0 ms 204 KB Output is correct
30 Correct 801 ms 4008 KB Output is correct
31 Correct 722 ms 3864 KB Output is correct
32 Correct 703 ms 3780 KB Output is correct
33 Correct 25 ms 1612 KB Output is correct
34 Correct 46 ms 2212 KB Output is correct
35 Correct 47 ms 2152 KB Output is correct
36 Correct 35 ms 2244 KB Output is correct
37 Correct 37 ms 2176 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 36 ms 852 KB Output is correct
18 Correct 37 ms 800 KB Output is correct
19 Correct 36 ms 776 KB Output is correct
20 Correct 3 ms 460 KB Output is correct
21 Correct 5 ms 588 KB Output is correct
22 Correct 5 ms 588 KB Output is correct
23 Correct 7 ms 616 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 801 ms 4008 KB Output is correct
26 Correct 722 ms 3864 KB Output is correct
27 Correct 703 ms 3780 KB Output is correct
28 Correct 25 ms 1612 KB Output is correct
29 Correct 46 ms 2212 KB Output is correct
30 Correct 47 ms 2152 KB Output is correct
31 Correct 35 ms 2244 KB Output is correct
32 Correct 37 ms 2176 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 0 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 0 ms 204 KB Output is correct
38 Runtime error 20 ms 8248 KB Execution killed with signal 6
39 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 844 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 168 ms 23184 KB Output is correct
8 Correct 340 ms 49928 KB Output is correct
9 Correct 345 ms 50224 KB Output is correct
10 Correct 368 ms 50300 KB Output is correct
11 Correct 192 ms 25028 KB Output is correct
12 Correct 417 ms 47192 KB Output is correct
13 Correct 459 ms 50372 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 36 ms 852 KB Output is correct
18 Correct 37 ms 800 KB Output is correct
19 Correct 36 ms 776 KB Output is correct
20 Correct 3 ms 460 KB Output is correct
21 Correct 5 ms 588 KB Output is correct
22 Correct 5 ms 588 KB Output is correct
23 Correct 7 ms 616 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 801 ms 4008 KB Output is correct
26 Correct 722 ms 3864 KB Output is correct
27 Correct 703 ms 3780 KB Output is correct
28 Correct 25 ms 1612 KB Output is correct
29 Correct 46 ms 2212 KB Output is correct
30 Correct 47 ms 2152 KB Output is correct
31 Correct 35 ms 2244 KB Output is correct
32 Correct 37 ms 2176 KB Output is correct
33 Runtime error 20 ms 8248 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -