Submission #1066235

#TimeUsernameProblemLanguageResultExecution timeMemory
1066235arbuzickRectangles (IOI19_rect)C++17
100 / 100
2319 ms969508 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; constexpr int inf = 1e9 + 7; struct SegmentTree { int R; vector<int> mn, mx; SegmentTree(vector<int> vals) { R = 1; while (R < (int)vals.size()) { R *= 2; } mn.assign(R * 2, inf); mx.assign(R * 2, -inf); for (int i = 0; i < (int)vals.size(); ++i) { mn[i + R] = mx[i + R] = vals[i]; } for (int i = R - 1; i > 0; --i) { mn[i] = min(mn[i * 2], mn[i * 2 + 1]); mx[i] = max(mx[i * 2], mx[i * 2 + 1]); } } pair<int, int> get(int l, int r) { l += R; r += R; pair<int, int> ans = make_pair(inf, -inf); while (l < r) { if (l & 1) { ans.first = min(ans.first, mn[l]); ans.second = max(ans.second, mx[l]); l++; } if (r & 1) { --r; ans.first = min(ans.first, mn[r]); ans.second = max(ans.second, mx[r]); } l >>= 1; r >>= 1; } return ans; } }; long long count_rectangles(vector<vector<int>> a) { int n = a.size(), m = a[0].size(); vector<vector<int>> up(n, vector<int>(m, -1)), down(n, vector<int>(m, n)), left(n, vector<int>(m, -1)), right(n, vector<int>(m, m)); for (int i = 0; i < n; ++i) { vector<int> st; for (int j = 0; j < m; ++j) { while (!st.empty() && a[i][st.back()] <= a[i][j]) { right[i][st.back()] = j; st.pop_back(); } st.push_back(j); } st.clear(); for (int j = m - 1; j >= 0; --j) { while (!st.empty() && a[i][st.back()] <= a[i][j]) { left[i][st.back()] = j; st.pop_back(); } st.push_back(j); } } for (int j = 0; j < m; ++j) { vector<int> st; for (int i = 0; i < n; ++i) { while (!st.empty() && a[st.back()][j] <= a[i][j]) { down[st.back()][j] = i; st.pop_back(); } st.push_back(i); } st.clear(); for (int i = n - 1; i >= 0; --i) { while (!st.empty() && a[st.back()][j] <= a[i][j]) { up[st.back()][j] = i; st.pop_back(); } st.push_back(i); } } vector<SegmentTree> upTree, downTree, leftTree, rightTree; for (int i = 0; i < n; ++i) { upTree.emplace_back(up[i]); downTree.emplace_back(down[i]); } for (int j = 0; j < m; ++j) { vector<int> leftNw, rightNw; for (int i = 0; i < n; ++i) { leftNw.push_back(left[i][j]); rightNw.push_back(right[i][j]); } leftTree.emplace_back(leftNw); rightTree.emplace_back(rightNw); } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { up[i][j] = -1; down[i][j] = n; left[i][j] = -1; right[i][j] = m; } } for (int i = 0; i < n; ++i) { vector<int> st; for (int j = 0; j < m; ++j) { while (!st.empty() && a[i][st.back()] < a[i][j]) { right[i][st.back()] = j; st.pop_back(); } st.push_back(j); } st.clear(); for (int j = m - 1; j >= 0; --j) { while (!st.empty() && a[i][st.back()] < a[i][j]) { left[i][st.back()] = j; st.pop_back(); } st.push_back(j); } } for (int j = 0; j < m; ++j) { vector<int> st; for (int i = 0; i < n; ++i) { while (!st.empty() && a[st.back()][j] < a[i][j]) { down[st.back()][j] = i; st.pop_back(); } st.push_back(i); } st.clear(); for (int i = n - 1; i >= 0; --i) { while (!st.empty() && a[st.back()][j] < a[i][j]) { up[st.back()][j] = i; st.pop_back(); } st.push_back(i); } } vector<pair<pair<int, int>, pair<int, int>>> rects; for (int i = 1; i + 1 < n; ++i) { for (int j = 1; j + 1 < m; ++j) { if (up[i][j] != -1 && down[i][j] != n && left[i][j] != -1 && right[i][j] != m) { rects.emplace_back(make_pair(up[i][j], left[i][j]), make_pair(down[i][j], right[i][j])); } } } sort(rects.begin(), rects.end()); rects.resize(unique(rects.begin(), rects.end()) - rects.begin()); long long ans = 0; for (int i = 0; i < (int)rects.size(); ++i) { int u = rects[i].first.first, l = rects[i].first.second, d = rects[i].second.first, r = rects[i].second.second; if (downTree[u].get(l + 1, r).first >= d && upTree[d].get(l + 1, r).second <= u && rightTree[l].get(u + 1, d).first >= r && leftTree[r].get(u + 1, d).second <= l) { ans++; } } return ans; }
#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...