Submission #1209618

#TimeUsernameProblemLanguageResultExecution timeMemory
1209618jer033Rectangles (IOI19_rect)C++20
59 / 100
5072 ms901956 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; const int INF = 9'900'000; vector<int> lo_range; vector<int> hi_range; struct dset { set<int> regular; set<int> inverted; void insert_both(int (&a)) { regular.insert(a); inverted.insert(0-a); } void get_range(int (&a)) { int hi = *(regular.upper_bound(a)); int lo = 0-*(inverted.upper_bound(0-a)); lo_range[a] = lo; hi_range[a] = hi; } dset(int a, int b) { regular = {}; inverted = {}; insert_both(a); insert_both(b); } void process_same_height(vector<int> (&x)) { for (int a: x) get_range(a); for (int a: x) insert_both(a); } }; /* struct cell { int r; int c; int lor, hir; int loc, hic; vector<int> rbased; vector<int> cbased; bool valid; void update() { rbased = {lor, hir, c, r}; cbased = {loc, hic, r, c}; valid = 1; } void check_validity_r(int min_r, int max_r) { if (lor < (min_r-1)) { valid = 0; //cout << r << ' ' << c << " disqualified by check_validity_r\n"; } if (hir > (max_r+1)) { valid = 0; //cout << r << ' ' << c << " disqualified by check_validity_r\n"; } } void check_validity_c(int min_c, int max_c) { if (loc < (min_c-1)) { valid = 0; //cout << r << ' ' << c << " disqualified by check_validity_c\n"; } if (hic > (max_c+1)) { valid = 0; //cout << r << ' ' << c << " disqualified by check_validity_c\n"; } } };*/ using cell = vector<int>; cell cbased(cell (&a)) { return {a[4], a[5], a[0], a[1], a[2], a[3]}; } cell rbased(cell (&a)) { return {a[2], a[3], a[1], a[0], a[4], a[5]}; } vector<vector< cell >> grid; vector<vector<bool>> valid; void check_validity_r(cell (&x), int min_r, int max_r) { if (x[4] < (min_r-1)) valid[x[2]][x[3]] = 0; if (x[5] > (max_r+1)) valid[x[2]][x[3]] = 0; } void check_validity_c(cell (&x), int min_c, int max_c) { if (x[4] < (min_c-1)) valid[x[3]][x[2]] = 0; if (x[5] > (max_c+1)) valid[x[3]][x[2]] = 0; } void c_process(vector<vector<int>> (&x)) { int siz = x.size(); x.push_back({-1, -1, INF, INF, -1, -1}); int curr_l = 0; int curr_r = 0; for (int i=1; i<=siz; i++) { if ((x[i][2] - x[i-1][2]) <= 1) curr_r = i; else { int range_l = x[curr_l][2]; int range_r = x[curr_r][2]; for (int j=curr_l; j<=curr_r; j++) check_validity_r(x[j], range_l, range_r); //grid[x[j][2]][x[j][3]].check_validity_r(range_l, range_r); curr_l = i; curr_r = i; } } } void r_process(vector<vector<int>> (&x)) { int siz = x.size(); x.push_back({-1, -1, INF, INF, -1, -1}); int curr_l = 0; int curr_r = 0; for (int i=1; i<=siz; i++) { if ((x[i][2] - x[i-1][2]) <= 1) curr_r = i; else { int range_l = x[curr_l][2]; int range_r = x[curr_r][2]; for (int j=curr_l; j<=curr_r; j++) check_validity_c(x[j], range_l, range_r); //grid[x[j][3]][x[j][2]].check_validity_c(range_l, range_r); curr_l = i; curr_r = i; } } } long long count_rectangles(std::vector< std::vector<int> > a) { int n = a.size(); int m = a[0].size(); //phase 1: fill the grid of cells with the info i need grid = vector<vector<cell>> (n, vector<cell> (m, vector<int> (6))); for (int i=0; i<n; i++) for (int j=0; j<m; j++) { grid[i][j][0]=i; grid[i][j][1]=j; } for (int row = 0; row<n; row++) { dset worker(-1, m); vector<pair<int, int>> row_heights(m); for (int j = 0; j<m; j++) row_heights[j] = {a[row][j], j}; sort(row_heights.begin(), row_heights.end(), greater<pair<int, int>>()); row_heights.push_back({-1, -1}); lo_range = vector<int> (m); hi_range = vector<int> (m); vector<int> to_insert = {row_heights[0].second}; to_insert.reserve(m); for (int k=1; k<=m; k++) { if (row_heights[k-1].first == row_heights[k].first) to_insert.push_back(row_heights[k].second); else { worker.process_same_height(to_insert); to_insert = {row_heights[k].second}; } } for (int j = 0; j<m; j++) { grid[row][j][4] = lo_range[j]; grid[row][j][5] = hi_range[j]; } } for (int col = 0; col<m; col++) { dset worker(-1, n); vector<pair<int, int>> col_heights(n); for (int i = 0; i<n; i++) col_heights[i] = {a[i][col], i}; sort(col_heights.begin(), col_heights.end(), greater<pair<int, int>>()); col_heights.push_back({-1, -1}); lo_range = vector<int> (n); hi_range = vector<int> (n); vector<int> to_insert = {col_heights[0].second}; to_insert.reserve(n); for (int k=1; k<=n; k++) { if (col_heights[k-1].first == col_heights[k].first) to_insert.push_back(col_heights[k].second); else { worker.process_same_height(to_insert); to_insert = {col_heights[k].second}; } } for (int i = 0; i<n; i++) { grid[i][col][2] = lo_range[i]; grid[i][col][3] = hi_range[i]; } } /*for (int i=0; i<n; i++) for (int j=0; j<m; j++) { grid[i][j].update(); cell x = grid[i][j]; //cout << x.r << ' ' << x.c << ' ' << x.lor << ' ' << x.hir << ' ' << x.loc << ' ' << x.hic << '\n'; }*/ //phase 2 valid = vector<vector<bool>> (n, vector<bool> (m, 1)); vector<vector<int>> cbasedlist; cbasedlist.reserve(m*n+1); for (int i=0; i<n; i++) for (int j=0; j<m; j++) cbasedlist.push_back(cbased(grid[i][j])); sort(cbasedlist.begin(), cbasedlist.end()); cbasedlist.push_back({-1, -1, -1, -1}); vector<vector<int>> to_process = {cbasedlist[0]}; to_process.reserve(m*n+1); for (int ij = 1; ij <= (m*n); ij++) { if ((cbasedlist[ij][0]==cbasedlist[ij-1][0]) and (cbasedlist[ij][1]==cbasedlist[ij-1][1])) to_process.push_back(cbasedlist[ij]); else { c_process(to_process); to_process = {cbasedlist[ij]}; } } cbasedlist.clear(); vector<vector<int>> rbasedlist; rbasedlist.reserve(m*n+1); for (int i=0; i<n; i++) for (int j=0; j<m; j++) rbasedlist.push_back(rbased(grid[i][j])); sort(rbasedlist.begin(), rbasedlist.end()); rbasedlist.push_back({-1, -1, -1, -1}); to_process = {rbasedlist[0]}; for (int ij = 1; ij <= (m*n); ij++) { if ((rbasedlist[ij][0]==rbasedlist[ij-1][0]) and (rbasedlist[ij][1]==rbasedlist[ij-1][1])) to_process.push_back(rbasedlist[ij]); else { r_process(to_process); to_process = {rbasedlist[ij]}; } } rbasedlist.clear(); //finding answer set<vector<int>> valid_rectangles; for (int i=1; i<(n-1); i++) for (int j=1; j<(m-1); j++) { cell x = grid[i][j]; if (valid[i][j] and (x[2]!=-1) and (x[3]!=n) and (x[4]!=-1) and (x[5]!=m)) { valid_rectangles.insert({x[2], x[3], x[4], x[5]}); //cout << x.lor << ' ' << x.hir << ' ' << x.loc << ' ' << x.hic << '\n'; } } long long answer = valid_rectangles.size(); return answer; }
#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...