Submission #836999

#TimeUsernameProblemLanguageResultExecution timeMemory
836999finn__Rectangles (IOI19_rect)C++17
0 / 100
22 ms980 KiB
#include <bits/stdc++.h> #include "rect.h" using namespace std; using L = long long; constexpr size_t N = 700; int16_t p[N][N], q[N][N], r[N][N], s[N][N]; bitset<N> rowwise[N], colwise[N], mask[N]; L count_rectangles(vector<vector<int>> a) { int16_t const n = a.size(), m = a[0].size(); for (int16_t i = 0; i < n; ++i) for (int16_t j = 0; j < m; ++j) { p[i][j] = j + 1; q[i][j] = j - 1; r[i][j] = i + 1; s[i][j] = i - 1; while (p[i][j] < m && a[i][p[i][j]] < a[i][j]) ++p[i][j]; while (q[i][j] >= 0 && a[i][q[i][j]] < a[i][j]) --q[i][j]; while (r[i][j] < n && a[r[i][j]][j] < a[i][j]) ++r[i][j]; while (s[i][j] >= 0 && a[s[i][j]][j] < a[i][j]) --s[i][j]; } vector<pair<int16_t, int16_t>> left_end, top_end; for (int16_t i = 1; i + 1 < n; ++i) for (int16_t j = 2; j < m; ++j) left_end.emplace_back(i, j); for (int16_t i = 2; i < n; ++i) for (int16_t j = 1; j + 1 < m; ++j) top_end.emplace_back(i, j); sort(left_end.begin(), left_end.end(), [](auto const &a, auto const &b) { return q[a.first][a.second] < q[b.first][b.second]; }); sort(top_end.begin(), top_end.end(), [](auto const &a, auto const &b) { return s[a.first][a.second] < s[b.first][b.second]; }); for (int16_t i = 0; i < N; ++i) for (int16_t j = 0; j <= i; ++j) mask[i][j] = 1; L ans = 0; auto it = top_end.begin(); for (int16_t i = 0; i + 2 < n; ++i) { while (it < top_end.end() && s[it->first][it->second] <= i) colwise[it->first][it->second] = 1, ++it; for (bitset<N> &b : rowwise) b.reset(); auto jt = left_end.begin(); for (int16_t j = 0; j + 2 < m; ++j) { while (jt < left_end.end() && q[jt->first][jt->second] <= j) rowwise[jt->first][jt->second] = 1, ++jt; vector<int16_t> top_limitation; for (int16_t k = m - 1; k > j; --k) { while (!top_limitation.empty() && r[i][k] <= r[i][top_limitation.back()]) top_limitation.pop_back(); top_limitation.push_back(k); } bitset<N> possible; for (int16_t k = j + 2; k < m; ++k) possible[k] = 1; for (int16_t k = i + 1; k + 1 < n; ++k) { possible &= mask[p[k][j + 1]]; possible &= rowwise[k]; while (!top_limitation.empty() && k >= r[i][top_limitation.back()]) { possible &= mask[top_limitation.back()]; top_limitation.pop_back(); } L c = (possible & mask[(~colwise[k + 1])._Find_next(j)]).count(); ans += c; } } } return ans; }

Compilation message (stderr)

rect.cpp: In function 'L count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int16_t' {aka 'short int'} and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   45 |     for (int16_t i = 0; i < N; ++i)
      |                         ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...