제출 #318054

#제출 시각아이디문제언어결과실행 시간메모리
318054MetBRectangles (IOI19_rect)C++14
100 / 100
2743 ms990124 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; int n, m, t; pair <int, int> hor_l[2500][2500], hor_r[2500][2500]; pair <int, int> ver_u[2500][2500], ver_d[2500][2500]; vector < array <int, 4> > v; vector < array <int, 4> > bucket[2500]; struct window : vector < pair <int, int> > { void append (int x) { while (!empty () && back ().first < x) pop_back (); } }; void check_above (pair <int, int>& p, int i, int l, int r) { if (!i) return; if (hor_l[i-1][r].first == l) p.second += hor_l[i-1][r].second; else if (hor_r[i-1][l].first == r) p.second += hor_r[i-1][l].second; } void check_left (pair <int, int>& p, int u, int d, int j) { if (!j) return; if (ver_d[u][j-1].first == d) p.second += ver_d[u][j-1].second; else if (ver_u[d][j-1].first == u) p.second += ver_u[d][j-1].second; } void check_rectangle (vector < vector <int> >& a, int x1, int y1, int x2, int y2) { if (x2 - x1 < 2 || y2 - y1 < 2) return; int hor_size, ver_size; if (a[x2-1][y1] <= a[x2-1][y2]) { if (hor_r[x2-1][y1].first != y2) return; ver_size = hor_r[x2-1][y1].second; } else { if (hor_l[x2-1][y2].first != y1) return; ver_size = hor_l[x2-1][y2].second; } if (a[x1][y2-1] <= a[x2][y2-1]) { if (ver_d[x1][y2-1].first != x2) return; hor_size = ver_d[x1][y2-1].second; } else { if (ver_u[x2][y2-1].first != x1) return; hor_size = ver_u[x2][y2-1].second; } if ((hor_size >= y2 - y1 - 1) && (ver_size >= x2 - x1 - 1)) { //cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << ver_u[x2][y2-1].first << endl; v.push_back ({x1, y1, x2, y2}); } } void check_position (vector< vector <int> >& a, int i, int l, int r) { int x; if (r - l < 2) return; x = ver_u[i+1][l+1].first; if (x != -1) check_rectangle (a, x, l, i + 1, r); x = ver_d[i-1][l+1].first; if (x != -1) check_rectangle (a, i - 1, l, x, r); x = ver_u[i+1][r-1].first; if (x != -1) check_rectangle (a, x, l, i + 1, r); x = ver_d[i-1][r-1].first; if (x != -1) check_rectangle (a, i - 1, l, x, r); } ll count_bruteforce (vector <vector <int>>& a) { int ans = 0; for (int i = 1; i < n - 1; i++) for (int j = 1; j < m - 1; j++) for (int i1 = i; i1 < n - 1; i1++) for (int j1 = j; j1 < m - 1; j1++) { bool k = true; for (int i0 = i; i0 <= i1; i0++) for (int j0 = j; j0 <= j1; j0++) { if (a[i0][j0] >= a[i-1][j0] || a[i0][j0] >= a[i1+1][j0] || a[i0][j0] >= a[i0][j-1] || a[i0][j0] >= a[i0][j1+1]) k = false; } if (k) { ans++; } } return ans; } ll count_rectangles (vector<vector<int> > a) { n = a.size (), m = a[0].size (); while (true) { //for (int i = 0; i < n; i++) // for (int j = 0; j < m; j++) // a[i][j] = rand () % 11; window s; for (int i = 0; i < n; i++) { s.clear (); for (int j = 0; j < m; j++) { s.append (a[i][j]); if (!s.empty ()) { int l = s.back ().second, r = j; hor_l[i][r].first = l; hor_l[i][r].second = 1; check_above (hor_l[i][r], i, l, r); } else hor_l[i][j].first = -1; s.push_back ({a[i][j], j}); } s.clear (); for (int j = m - 1; j >= 0; j--) { s.append (a[i][j]); if (!s.empty ()) { int l = j, r = s.back ().second; hor_r[i][l].first = r; hor_r[i][l].second = 1; check_above (hor_r[i][l], i, l, r); } else hor_r[i][j].first = -1; s.push_back ({a[i][j], j}); } } for (int j = 0; j < m; j++) { s.clear (); for (int i = 0; i < n; i++) { s.append (a[i][j]); if (!s.empty ()) { int u = s.back ().second, d = i; ver_u[d][j].first = u; ver_u[d][j].second = 1; check_left (ver_u[d][j], u, d, j); } else ver_u[i][j].first = -1; s.push_back ({a[i][j], i}); } s.clear (); for (int i = n - 1; i >= 0; i--) { s.append (a[i][j]); if (!s.empty ()) { int u = i, d = s.back ().second; ver_d[u][j].first = d; ver_d[u][j].second = 1; check_left (ver_d[u][j], u, d, j); } else ver_d[i][j].first = -1; s.push_back ({a[i][j], i}); } } for (int i = 1; i < n - 1; i++) { for (int j = 0; j < m; j++) { if (hor_l[i][j].first != -1) check_position (a, i, hor_l[i][j].first, j); if (hor_r[i][j].first != -1) check_position (a, i, j, hor_r[i][j].first); } } for (int k = 0; k < 4; k++) { for (int i = 0; i < max (n, m); i++) bucket[i].clear (); for (auto&& a : v) { bucket[a[k]].push_back (a); } v.clear (); for (int i = 0; i < max (n, m); i++) for (auto&& a : bucket[i]) v.push_back (a); } int cnt = 0; for (int i = 0; i < (int) v.size (); i++) if (!i || v[i-1] != v[i]) cnt++; v.clear (); int cnt2 = cnt; t++; if (t % 100 == 0) cout << t << endl; //cout << cnt << ' ' << cnt2 << endl; if (cnt != cnt2) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) cout << a[i][j] << ' '; cout << '\n'; } return cnt; } return cnt; } }
#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...