제출 #810405

#제출 시각아이디문제언어결과실행 시간메모리
810405NothingXDRectangles (IOI19_rect)C++17
100 / 100
2482 ms728616 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef double ld; void debug_out(){cerr<<endl;} template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cerr << H << ' '; debug_out(T...); } #define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__) #define F first #define S second #define all(x) x.begin(), x.end() #define MP(x, y) make_pair(x, y) const int maxn = 3e3 + 10; const int lg = 20; int n, m, spt[lg][maxn], a[maxn][maxn], l[maxn][maxn], r[maxn][maxn], u[maxn][maxn], d[maxn][maxn], ans[maxn][maxn]; int L[maxn][maxn], R[maxn][maxn], U[maxn][maxn], D[maxn][maxn]; vector<pii> Q[maxn][4]; struct rect{ int a, b, c, d; }; int getmin(int l, int r){ r++; int x = 31 - __builtin_clz(r-l); return min(spt[x][l], spt[x][r-(1<<x)]); } int getmax(int l, int r){ r++; int x = 31 - __builtin_clz(r-l); return max(spt[x][l], spt[x][r-(1<<x)]); } ll count_rectangles(vector<vector<int>> A) { n = A.size(); m = A[0].size(); //debug(n, m); for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ a[i][j] = A[i][j]; // debug(i, j, a[i][j]); } } // debug(1); for (int i = 0; i < n; i++){ vector<int> v; for (int j = 0; j < m; j++){ l[i][j] = -1; while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back(); if (!v.empty()) l[i][j] = v.back(); v.push_back(j); } v.clear(); for (int j = m-1; ~j; j--){ r[i][j] = m; while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back(); if (!v.empty()){ r[i][j] = v.back(); // debug(i, j, v.back(), a[i][j], a[i][v.back()]); } v.push_back(j); } } // debug(2); for (int j = 0; j < m; j++){ vector<int> v; for (int i = 0; i < n; i++){ u[i][j] = -1; while (!v.empty() && a[v.back()][j] <= a[i][j]) v.pop_back(); if (!v.empty()) u[i][j] = v.back(); v.push_back(i); } v.clear(); for (int i = n-1; ~i; i--){ d[i][j] = n; while (!v.empty() && a[v.back()][j] <= a[i][j]){ //debug(i, j, v.back(), a[v.back()][j], a[i][j]); v.pop_back(); } if (!v.empty()) d[i][j] = v.back(); v.push_back(i); } } // debug(3); for (int x = 0; x < n; x++){ for (int y = 0; y < m; y++){ // debug(x, y, l[x][y], r[x][y], u[x][y], d[x][y]); if (l[x][y] == -1 || r[x][y] == m || d[x][y] == n || u[x][y] == -1) continue; // debug(1); Q[l[x][y]][0].push_back({x, y}); Q[r[x][y]][1].push_back({x, y}); Q[u[x][y]][2].push_back({x, y}); Q[d[x][y]][3].push_back({x, y}); } } for (int i = 0; i < n; i++){ vector<int> v; for (int j = 0; j < m; j++){ L[i][j] = -1; while (!v.empty() && a[i][v.back()] < a[i][j]) v.pop_back(); if (!v.empty()) L[i][j] = v.back(); v.push_back(j); } v.clear(); for (int j = m-1; ~j; j--){ R[i][j] = m; while (!v.empty() && a[i][v.back()] < a[i][j]) v.pop_back(); if (!v.empty()){ R[i][j] = v.back(); // debug(i, j, v.back(), a[i][j], a[i][v.back()]); } v.push_back(j); } } // debug(2); for (int j = 0; j < m; j++){ vector<int> v; for (int i = 0; i < n; i++){ U[i][j] = -1; while (!v.empty() && a[v.back()][j] < a[i][j]) v.pop_back(); if (!v.empty()) U[i][j] = v.back(); v.push_back(i); } v.clear(); for (int i = n-1; ~i; i--){ D[i][j] = n; while (!v.empty() && a[v.back()][j] < a[i][j]){ //debug(i, j, v.back(), a[v.back()][j], a[i][j]); v.pop_back(); } if (!v.empty()) D[i][j] = v.back(); v.push_back(i); } } // debug(4); for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ spt[0][j] = U[i][j]; } for (int j = 1; j < lg; j++){ for (int k = 0; k + (1 << j) <= m; k++){ spt[j][k] = max(spt[j-1][k], spt[j-1][k+(1<<(j-1))]); } } for (auto [x, y]: Q[i][3]){ if (getmax(l[x][y]+1, r[x][y]-1) <= u[x][y]) ans[x][y]++; } for (int j = 0; j < m; j++){ spt[0][j] = D[i][j]; } for (int j = 1; j < lg; j++){ for (int k = 0; k + (1 << j) <= m; k++){ spt[j][k] = min(spt[j-1][k], spt[j-1][k+(1<<(j-1))]); } } for (auto [x, y]: Q[i][2]){ if (getmin(l[x][y]+1, r[x][y]-1) >= d[x][y]) ans[x][y]++; } } // debug(5); for (int j = 0; j < m; j++){ // debug(j); for (int i = 0; i < n; i++){ spt[0][i] = L[i][j]; } for (int i = 1; i < lg; i++){ for (int k = 0; k + (1 << i) <= n; k++){ spt[i][k] = max(spt[i-1][k], spt[i-1][k+(1<<(i-1))]); } } // debug(1); for (auto [x, y]: Q[j][1]){ if (getmax(u[x][y]+1, d[x][y]-1) <= l[x][y]) ans[x][y]++; } // debug(2); for (int i = 0; i < n; i++){ spt[0][i] = R[i][j]; } for (int i = 1; i < lg; i++){ for (int k = 0; k + (1 << i) <= n; k++){ spt[i][k] = min(spt[i-1][k], spt[i-1][k+(1<<(i-1))]); } } // debug(3); for (auto [x, y]: Q[j][0]){ if (getmin(u[x][y]+1, d[x][y]-1) >= r[x][y]) ans[x][y]++; } // debug(4); } vector<pair<pii,pii>> res; for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ if (ans[i][j] == 4) res.push_back({{l[i][j]+1, r[i][j]-1}, {u[i][j]+1, d[i][j]-1}}); } } sort(all(res)); res.resize(distance(res.begin(), unique(all(res)))); /*for (auto [a, b]: res){ debug(a.F, a.S, b.F, b.S); }*/ return res.size(); }
#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...