Submission #412296

#TimeUsernameProblemLanguageResultExecution timeMemory
412296timmyfengRectangles (IOI19_rect)C++17
0 / 100
360 ms413308 KiB
#include <bits/stdc++.h> using namespace std; #include <bits/extc++.h> template <class T, class Comp = less<T>> using ordered_set = __gnu_pbds::tree< T, __gnu_pbds::null_type, Comp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update >; const int N = 1000; ordered_set<int> where_h[N][N], where_v[N][N]; vector<int> jump_h[N][N], jump_v[N][N]; bool check(ordered_set<int> &s, int a, int b) { return (int) (s.order_of_key(b + 1) - s.order_of_key(a)) == b - a + 1; } long long count_rectangles(vector<vector<int>> a) { int n = a.size(), m = a[0].size(); for (int i = 0; i < n; ++i) { vector<int> mono; for (int j = 0; j < m; ++j) { while (!mono.empty() && a[i][mono.back()] < a[i][j]) { jump_h[i][mono.back() + 1].push_back(j - 1); where_h[mono.back() + 1][j - 1].insert(i); mono.pop_back(); } if (!mono.empty()) { jump_h[i][mono.back() + 1].push_back(j - 1); where_h[mono.back() + 1][j - 1].insert(i); } mono.push_back(j); } } for (int i = 0; i < m; ++i) { vector<int> mono; for (int j = 0; j < n; ++j) { while (!mono.empty() && a[mono.back()][i] < a[j][i]) { jump_v[mono.back() + 1][i].push_back(j - 1); where_v[mono.back() + 1][j - 1].insert(i); mono.pop_back(); } if (!mono.empty()) { jump_v[mono.back() + 1][i].push_back(j - 1); where_v[mono.back() + 1][j - 1].insert(i); } mono.push_back(j); } } int ans = 0; for (int i1 = 0; i1 < n; ++i1) { for (int j1 = 0; j1 < m; ++j1) { for (auto i2 : jump_v[i1][j1]) { for (auto j2 : jump_h[i1][j1]) { if (i1 <= i2 && j1 <= j2) { ans += check(where_v[i1][i2], j1, j2) && check(where_h[j1][j2], i1, i2); } } } } } 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...