Submission #1215422

#TimeUsernameProblemLanguageResultExecution timeMemory
1215422brintonRectangles (IOI19_rect)C++20
59 / 100
1472 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 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 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; vector<vector<short>> horivalid(M,vector<short>(M,0)); for(int bottom = 1;bottom+1 < N;bottom++){ vector<vector<short>> newHori(M,vector<short>(M,0)); for(int l = 0;l+2 < M;l++){ int cmax = a[bottom][l+1]; for(int r = l+2;r < M;r++){ if(cmax < a[bottom][l] && cmax < a[bottom][r]){ newHori[l][r] = true; } cmax = max(cmax,a[bottom][r]); if(a[bottom][l] <= cmax) break; } } for(int l = 0;l < M;l++){ for(int r = 0;r < M;r++){ if(newHori[l][r]){ newHori[l][r] += horivalid[l][r]; } } } swap(newHori,horivalid); for(int l = 0;l+2 < M;l++){ for(int r = l+2;r < M;r++){ int minTop = max(0,bottom-horivalid[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...