Submission #1215195

#TimeUsernameProblemLanguageResultExecution timeMemory
1215195jasonicRectangles (IOI19_rect)C++20
8 / 100
5093 ms572004 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fastIO cin.tie(0); ios::sync_with_stdio(false) struct ST{ int l, r; ST *lt, *rt; int mx; void comb() { mx = max(lt->mx, rt->mx); } ST(int bl, int br, vector<int> &a) { lt = rt = nullptr; l = bl, r = br; if(l == r) { mx = a[l]; } else { int m = (l+r)/2; lt = new ST(l, m, a); rt = new ST(m+1, r, a); comb(); } } int qry(int ql, int qr) { if(qr < l || r < ql) return -1; if(ql <= l && r <= qr) return mx; else return max(lt->qry(ql, qr), rt->qry(ql, qr)); } }; ll count_rectangles(vector<vector<int>> arr) { int r = size(arr); int c = size(arr[0]); vector<vector<int>> rotatedArr(c, vector<int>(r, 0)); for(int i = 0; i < r; i++) { for(int j = 0; j < c; j++) { rotatedArr[j][i] = arr[i][j]; } } vector<ST> rows, cols; for(int i = 0; i < r; i++) { rows.push_back(ST(0, c-1, arr[i])); } for(int i = 0; i < c; i++) { cols.push_back(ST(0, r-1, rotatedArr[i])); } ll ans = 0; for(int yl = 1; yl < r-1; yl++) { for(int xl = 1; xl < c-1; xl++) { for(int yr = yl; yr < r-1; yr++) { for(int xr = xl; xr < c-1; xr++) { bool valid = true; for(int x = xl; x <= xr; x++) { valid &= min(arr[yl-1][x], arr[yr+1][x]) > cols[x].qry(yl, yr); } for(int y = yl; y <= yr; y++) { valid &= min(arr[y][xl-1], arr[y][xr+1]) > rows[y].qry(xl, xr); } ans += valid; } } } } 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...