제출 #823490

#제출 시각아이디문제언어결과실행 시간메모리
823490dxz05Rectangles (IOI19_rect)C++17
72 / 100
5045 ms618832 KiB
#pragma GCC optimize("Ofast,O3,unroll-loops") #pragma GCC target("avx,avx2") #include "rect.h" #include <bits/stdc++.h> using namespace std; vector<pair<int, int>> find_borders(const vector<int> &a){ int n = (int) a.size(); stack<int> st; vector<int> l(n), r(n); for (int i = 0; i < n; i++){ while (!st.empty() && a[st.top()] < a[i]) st.pop(); l[i] = (st.empty() ? -1 : st.top()); st.push(i); } while (!st.empty()) st.pop(); for (int i = n - 1; i >= 0; i--){ while (!st.empty() && a[st.top()] < a[i]) st.pop(); r[i] = (st.empty() ? n : st.top()); st.push(i); } vector<pair<int, int>> ans; set<pair<int, int>> s1; // (i, r[i]) set<pair<int, int>> s2; // (r[i], i) for (int j = 0; j < n; j++){ while (!s2.empty()){ int i = s2.begin()->second; if (r[i] < j){ s1.erase(make_pair(i, r[i])); s2.erase(make_pair(r[i], i)); } else { break; } } assert(s1.size() == s2.size()); auto it = s1.end(); while (true){ if (it == s1.begin()) break; it--; int i = it->first; if (i < l[j]) break; if (i + 1 < j) ans.emplace_back(i + 1, j - 1); } s1.emplace(j, r[j]); s2.emplace(r[j], j); } return ans; } const int MaxN = 2500; vector<pair<int, int>> per_col[MaxN][MaxN]; vector<pair<int, int>> per_row[MaxN][MaxN]; vector<tuple<int, int, int>> opening[MaxN]; vector<pair<int, int>> vals_to_add[MaxN]; long long count_rectangles(vector<vector<int>> A) { int n = (int) A.size(), m = (int) A[0].size(); for (int i = 1; i + 1 < n; i++){ vector<pair<int, int>> f = find_borders(A[i]); for (auto [l, r] : f){ auto &v = per_col[l][r]; if (v.empty() || v.back().second != i - 1){ v.emplace_back(i, i); } else { v.back().second++; } } } for (int j = 1; j + 1 < m; j++){ vector<int> col(n); for (int i = 0; i < n; i++) col[i] = A[i][j]; vector<pair<int, int>> f = find_borders(col); for (auto [x, y] : f){ auto &v = per_row[x][y]; if (v.empty() || v.back().second != j - 1){ v.emplace_back(j, j); } else { v.back().second++; } } } for (int x = 0; x < n; x++){ for (int y = x; y < n; y++){ for (auto [l, r] : per_row[x][y]){ opening[l].emplace_back(r, x, y); } } } long long ans = 0; for (int l = 1; l < m - 1; l++){ for (auto [r, x, y] : opening[l]){ vals_to_add[r].emplace_back(x, y); } vector<pair<int, int>> _vals; for (int r = m - 2; r >= l; r--){ for (auto [x, y] : vals_to_add[r]){ _vals.emplace_back(x, y); } vector<pair<int, int>> vals = _vals; vector<pair<int, int>> new_vals; for (auto [X, Y] : per_col[l][r]){ for (auto [x, y] : vals){ if (x > Y) new_vals.emplace_back(x, y); if (X <= x && y <= Y){ ans++; } } } vals.swap(new_vals); } } 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...