Submission #222953

#TimeUsernameProblemLanguageResultExecution timeMemory
222953MrDominoRectangles (IOI19_rect)C++14
50 / 100
5053 ms251544 KiB
#include <bits/stdc++.h> #include "rect.h" using namespace std; typedef long long ll; const int N = 2500 + 7; int v[N]; int stk[N]; int top; int l[N]; int r[N]; vector<pair<int, int>> potential(vector<int> b) { int n = (int) b.size(); for (int i = 1; i <= n;i ++) { v[i] = b[i - 1]; } top = 0; stk[0] = 0; for (int i = 1; i <= n; i++) { while (top && v[stk[top]] < v[i]) { top--; } l[i] = stk[top]; stk[++top] = i; } top = 0; stk[0] = n + 1; for (int i = n; i >= 1; i--) { while (top && v[stk[top]] < v[i]) { top--; } r[i] = stk[top]; stk[++top] = i; } vector<pair<int, int>> sol; for (int i = 1; i <= n; i++) { int j = l[i]; if (1 <= j && i - j >= 2) { sol.push_back({j, i}); } j = r[i]; if (j <= n && j - i >= 2) { sol.push_back({i, j}); } } for (auto &it : sol) { it.first--; it.second--; it.first++; it.second--; } if (sol.empty()) { return sol; } sort(sol.begin(), sol.end()); vector<pair<int, int>> sol2; sol2.push_back(sol[0]); for (int i = 1; i < (int) sol.size(); i++) { if (sol[i] != sol[i - 1]) { sol2.push_back(sol[i]); } } return sol2; } vector<vector<pair<int, int>>> pot_row; vector<vector<pair<int, int>>> pot_col; bool has(int c, int r1, int r2) { pair<int, int> it = {r1, r2}; int lo = 0; int hi = (int) pot_col[c].size() - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (pot_col[c][mid] == it) { return 1; } if (pot_col[c][mid] < it) { lo = mid + 1; } else { hi = mid - 1; } } return 0; } long long count_rectangles(vector<vector<int>> a) { int n = (int) a.size(); int m = (int) a[0].size(); pot_row.resize(n); pot_col.resize(m); for (int i = 0; i < n; i++) { pot_row[i] = potential(a[i]); } for (int j = 0; j < m; j++) { vector<int> b; for (int i = 0; i < n; i++) { b.push_back(a[i][j]); } pot_col[j] = potential(b); } vector<vector<vector<int>>> who_row(m); for (int i = 0; i < m; i++) { who_row[i].resize(m, {}); } for (int i = 0; i < n; i++) { for (auto &it : pot_row[i]) { int c1 = it.first; int c2 = it.second; who_row[c1][c2].push_back(i); } } ll sol = 0; for (int c1 = 0; c1 < m; c1++) { for (int c2 = c1; c2 < m; c2++) { vector<int> rows = who_row[c1][c2]; set<int> goods; if (rows.empty()) { continue; } int i = 0; while (i < (int) rows.size()) { int j = i; while (j + 1 < (int) rows.size() && rows[j + 1] == rows[j] + 1) { j++; } for (int k = i; k <= j; k++) { for (int k2 = k; k2 <= j; k2++) { int r1 = rows[k]; int r2 = rows[k2]; bool good = 1; for (int c = c1; c <= c2; c++) { if (has(c, r1, r2) == 0) { good = 0; break; } } if (good) { sol++; } } } i = j + 1; } } } return sol; }
#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...