Submission #439344

#TimeUsernameProblemLanguageResultExecution timeMemory
439344SortingRectangles (IOI19_rect)C++17
0 / 100
894 ms135720 KiB
#include "rect.h" #include <bits/stdc++.h> #pragma GCC optimize("O3") using namespace std; typedef long long ll; const int N = 2500 + 3; vector<vector<int>> a; int n, m; int u[N][N], d[N][N], l[N][N], r[N][N]; void init(){ stack<int> st; for(int j = 0; j < m; ++j){ for(int i = 0; i < n; ++i){ while(!st.empty() && a[i][j] > a[st.top()][j]){ d[st.top()][j] = i; st.pop(); } st.push(i); } while(!st.empty()){ d[st.top()][j] = n; st.pop(); } for(int i = n - 1; i >= 0; --i){ while(!st.empty() && a[i][j] > a[st.top()][j]){ u[st.top()][j] = i; st.pop(); } st.push(i); } while(!st.empty()){ u[st.top()][j] = -1; st.pop(); } } for(int i = 0; i < n; ++i){ for(int j = 0; j < m; ++j){ while(!st.empty() && a[i][j] > a[i][st.top()]){ r[i][st.top()] = j; st.pop(); } st.push(j); } while(!st.empty()){ r[i][st.top()] = m; st.pop(); } for(int j = n - 1; j >= 0; --j){ while(!st.empty() && a[i][j] > a[i][st.top()]){ l[i][st.top()] = j; st.pop(); } st.push(j); } while(!st.empty()){ l[i][st.top()] = -1; st.pop(); } } } bool check(int x1, int y1, int x2, int y2){ for(int i = x1; i <= x2; ++i) for(int j = y1; j <= y2; ++j) if(a[i][j] >= a[x1 - 1][j] || a[i][j] >= a[x2 + 1][j] || a[i][j] >= a[i][y1 - 1] || a[i][j] >= a[i][y2 + 1]) return false; return true; } long long count_rectangles(vector<vector<int>> _a) { swap(a, _a); n = a.size(), m = a[0].size(); init(); ll ans = 0; vector<array<int, 4>> v; for(int x = 1; x < n - 1; ++x) for(int y = 1; y < m - 1; ++y) v.push_back({u[x][y] + 1, l[x][y] + 1, d[x][y] - 1, r[x][y] - 1}); sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); for(auto [x1, y1, x2, y2]: v){ if(x1 <= 0 || y1 <= 0 || x2 >= n - 1 || y2 >= m - 1) continue; //cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl; ans += check(x1, y1, x2, y2); } 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...