제출 #1107897

#제출 시각아이디문제언어결과실행 시간메모리
1107897SharkyRectangles (IOI19_rect)C++17
0 / 100
123 ms148552 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; using ll = long long; vector<array<int, 2>> ed[2510]; vector<pair<int, int>> qr[2510]; ll fen[2510]; void upd(int u, int k) { for (; u <= 2500; u += (u & -u)) fen[u] += (ll) k; } ll query(int u) { ll res = 0; for (; u; u -= (u & -u)) res += fen[u]; return res; } ll count_rectangles(std::vector<std::vector<int>> inp) { int n = inp.size(), m = inp[0].size(); ll ans = 0; vector<vector<int>> a(n+1, vector<int> (m+1)); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) a[i][j] = inp[i-1][j-1]; vector<vector<vector<int>>> h(m+1, vector<vector<int>> (m+1)); vector<vector<vector<int>>> v(n+1, vector<vector<int>> (n+1)); for (int i = 1; i <= n; i++) { stack<int> st; for (int j = 1; j <= m; j++) { while (!st.empty() && a[i][st.top()] < a[i][j]) { if (st.top() + 1 < j) h[st.top() + 1][j - 1].push_back(i); st.pop(); } if (!st.empty() && st.top() + 1 < j) h[st.top() + 1][j - 1].push_back(i); st.push(j); } } for (int j = 1; j <= m; j++) { stack<int> st; for (int i = 1; i <= n; i++) { while (!st.empty() && a[st.top()][j] < a[i][j]) { if (st.top() + 1 < i) v[st.top() + 1][i - 1].push_back(j); st.pop(); } if (!st.empty() && st.top() + 1 < i) v[st.top() + 1][i - 1].push_back(j); st.push(i); } } vector<vector<vector<array<int, 3>>>> rrect(n+1, vector<vector<array<int, 3>>> (m+1)); vector<vector<vector<array<int, 3>>>> crect(n+1, vector<vector<array<int, 3>>> (m+1)); for (int c1 = 1; c1 <= m; c1++) { for (int c2 = c1; c2 <= m; c2++) { vector<pair<int, int>> pr; for (int& row : h[c1][c2]) { if (pr.empty() || pr.back().second + 1 != row) pr.push_back({row, row}); else pr.back().second++; } for (auto& [lb, rb] : pr) for (int i = lb; i <= rb; i++) crect[i][c1].push_back({c2, i, rb}); } } for (int r1 = 1; r1 <= n; r1++) { for (int r2 = r1; r2 <= n; r2++) { vector<pair<int, int>> pr; for (int& col : v[r1][r2]) { if (pr.empty() || pr.back().second + 1 != col) pr.push_back({col, col}); else pr.back().second++; } for (auto& [lb, rb] : pr) for (int i = lb; i <= rb; i++) rrect[r1][i].push_back({r2, i, rb}); } } for (int r1 = 1; r1 <= n; r1++) { for (int c1 = 1; c1 <= m; c1++) { vector<int> crit; for (auto& [r2, lb, rb] : rrect[r1][c1]) { crit.push_back(r2); qr[r2].push_back({lb, rb}); } for (auto& [c2, lb, rb] : crect[r1][c1]) { crit.push_back(lb); crit.push_back(rb + 1); ed[lb].push_back({1, c2}); ed[rb + 1].push_back({0, c2}); } sort(crit.begin(), crit.end()); crit.erase(unique(crit.begin(), crit.end()), crit.end()); for (auto& ti : crit) { for (auto& [x, y] : ed[ti]) { if (x) upd(y, 1); else upd(y, -1); } for (auto& [x, y] : qr[ti]) ans += query(y) - query(x-1); ed[ti].clear(); qr[ti].clear(); } } } 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...