제출 #1206327

#제출 시각아이디문제언어결과실행 시간메모리
1206327thelegendary08Rectangles (IOI19_rect)C++17
37 / 100
2488 ms1114112 KiB
#include "rect.h" #include<bits/stdc++.h> #define f0r(i,n) for(int i = 0; i<n; i++) #define FOR(i, k, n) for(int i = k; i<n; i++) #define pb push_back #define vi vector<int> #define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n'; #define dout(x) cout<<x<<' '<<#x<<'\n'; #define pii pair<int,int> #define vpii vector<pii> #define vb vector<bool> #define mp make_pair using namespace std; int n,m; vector<vector<signed>>grid; vpii adj(pii a){ int x = a.first; int y = a.second; vpii ret; if(x > 0 && grid[x-1][y] == 0){ ret.pb(mp(x-1, y)); } if(y > 0 && grid[x][y-1] == 0){ ret.pb(mp(x, y-1)); } if(x < n-1 && grid[x+1][y] == 0){ ret.pb(mp(x+1, y)); } if(y < m-1 && grid[x][y+1] == 0){ ret.pb(mp(x, y+1)); } return ret; } long long int count_rectangles(std::vector<std::vector<signed> > a) { grid = a; n = a.size(); m = a[0].size(); //subtask 1 //i * m + j vector<vector<bool>>mat(n*m, vb(n * m)); f0r(i, n){ f0r(j,m){ for(int k = i+1; k < n; k++){ if(a[i][j] <= a[k][j]){ mat[i*m+j][k*m+j] = 1; mat[k*m+j][i*m+j] = 1; break; } } for(int k = i-1; k >= 0; k--){ if(a[i][j] <= a[k][j]){ mat[i*m+j][k*m+j] = 1; mat[k*m+j][i*m+j] = 1; break; } } for(int k = j + 1; k<m; k++){ if(a[i][j] <= a[i][k]){ mat[i*m+j][i*m+k] = 1; mat[i*m+k][i*m+j]=1; break; } } for(int k = j-1; k>=0; k--){ if(a[i][j] <= a[i][k]){ mat[i*m+j][i*m+k] = 1; mat[i*m+k][i*m+j]=1; break; } } } } //fixj[k][l][i], make prefix sum vector<vector<vector<int>>>fixj(m, vector<vi>(m, vi(n+1))); f0r(k,m){ FOR(l, k+2, m){ for(int z = 1; z <= n; z++){ if(mat[(z-1)*m+k][(z-1)*m+l]){ fixj[k][l][z] = fixj[k][l][z-1] + 1; } else fixj[k][l][z] = fixj[k][l][z-1]; } } } vector<vector<vector<int>>>fixi(n, vector<vi>(n, vi(m+1))); f0r(i, n){ FOR(j, i+2, n){ for(int z = 1; z <= m; z++){ if(mat[i*m+z-1][j*m+z-1])fixi[i][j][z] = fixi[i][j][z-1] + 1; else fixi[i][j][z] = fixi[i][j][z-1]; } } } int ans = 0; f0r(i, n){ FOR(j, i+2, n){ f0r(k, m){ FOR(l, k+2, m){ bool ok = 1; /* for(int z = i+1; z < j; z++){ if(!mat[z*m+k][z*m+l])ok = 0; } for(int z = k+1; z < l; z++){ if(!mat[i*m+z][j*m+z])ok = 0; } */ //from i+1 to j-1 if(fixj[k][l][j] - fixj[k][l][i+1] != j-i-1)ok = 0; //from k+1 to l-1 if(fixi[i][j][l] - fixi[i][j][k+1] != l-k-1)ok = 0; if(ok)ans++; } } } } return ans; //subtask 5 /* if(n < 3)return 0; else{ int ans = 0; vi v; f0r(i,m){ if(a[0][i] > a[1][i] && a[1][i] < a[2][i])v.pb(1); else v.pb(0); } vi ps(m+1); FOR(i, 1, m+1){ ps[i] = ps[i-1] + v[i-1]; } f0r(i, m){ // dout(i); int run = -1; FOR(j, i+1, m){ if(run < a[1][j]){ run = a[1][j]; // dout(run); if(j != i + 1 && ps[j] - ps[i+1] == (j - i - 1))ans++; } if(a[1][j] >= a[1][i]){ break; } } } return ans; } */ //subtask 6 /* vector<vector<bool>>vis(n, vector<bool>(m)); int ans = 0; f0r(i,n){ f0r(j,m){ if(a[i][j] == 0 && !vis[i][j]){ queue<pii>q; int tot = 1; q.push(mp(i,j)); // cout<<i<<' '<<j<<'\n'; vis[i][j] = 1; int mnx = i; int mxx = i; int mny = j; int mxy = j; while(!q.empty()){ pii node = q.front(); q.pop(); for(auto u : adj(node)){ if(vis[u.first][u.second])continue; // cout<<u.first<<' '<<u.second<<'\n'; mnx = min(mnx, u.first); mxx = max(mxx, u.first); mny = min(mny, u.second); mxy = max(mxy, u.second); tot++; vis[u.first][u.second] = 1; q.push(mp(u.first, u.second)); } } int area = (mxx - mnx + 1) * (mxy - mny + 1); // cout<<"FINAL"<<' '<<area<<' '<<tot<<'\n'; if(mnx > 0 && mxx < n-1 && mny > 0 && mxy < m-1 && area == tot)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...