Submission #1215420

#TimeUsernameProblemLanguageResultExecution timeMemory
1215420brintonRectangles (IOI19_rect)C++20
37 / 100
493 ms1114112 KiB
#include <bits/stdc++.h> #include "rect.h" using namespace std; long long count_rectangles(vector<vector<int> > a) { int N = a.size(),M = a[0].size(); if(N < 3 || M < 3) return 0LL; vector<vector<vector<short>>> horivalid(N,vector<vector<short>>(M,vector<short>(M,0)));// i,l,r vector<vector<vector<short>>> vertvalid(M,vector<vector<short>>(N,vector<short>(N,0)));// j,l,r; for(int i = 0;i < N;i++){ for(int l = 0;l+2 < M;l++){ int cmax = a[i][l+1]; for(int r = l+2;r < M;r++){ if(cmax < a[i][l] && cmax < a[i][r]){ horivalid[i][l][r] = true; } cmax = max(cmax,a[i][r]); if(a[i][l] <= cmax) break; } } } for(int j = 0;j < M;j++){ for(int l = 0;l+2 < N;l++){ int cmax = a[l+1][j]; for(int r = l+2;r < N;r++){ if(cmax < a[l][j] && cmax < a[r][j]){ vertvalid[j][l][r] = true; } cmax = max(cmax,a[r][j]); if(a[l][j] <= cmax) break; } } } for(int i = 1;i < N;i++){ for(int l = 0;l < M;l++){ for(int r = 0;r < M;r++){ if(horivalid[i][l][r]){ horivalid[i][l][r] += horivalid[i-1][l][r]; } } } } for(int j = 1;j < M;j++){ for(int l = 0;l < N;l++){ for(int r = 0;r < N;r++){ if(vertvalid[j][l][r]){ vertvalid[j][l][r] += vertvalid[j-1][l][r]; } } } } long long ans = 0; for(int bottom = 1;bottom+1 < N;bottom++){ for(int l = 0;l+2 < M;l++){ for(int r = l+2;r < M;r++){ int minTop = max(0,bottom-horivalid[bottom][l][r]); int cbottom = bottom+1; for(int ctop = minTop;ctop < bottom;ctop++){ // cout << l+1 << " " << r-1 << " " << ctop+1 << " " << cbottom-1 << endl; if(vertvalid[r-1][ctop][cbottom] >= r-l-1) ans++; } } } } 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...