제출 #1068245

#제출 시각아이디문제언어결과실행 시간메모리
1068245pccRectangles (IOI19_rect)C++17
13 / 100
208 ms147816 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #pragma GCC target("avx2,popcnt,sse4") #pragma GCC optimize("O3,unroll-loops") #define ll long long vector<vector<int>> pref,arr,row,col; int N,M; int sum(int sr,int er,int sc,int ec){ sr++,er++,sc++,ec++; return pref[er][ec]-pref[sr-1][ec]-pref[er][sc-1]+pref[sr-1][sc-1]; } long long count_rectangles(std::vector<std::vector<int> > a) { N = a.size(),M = a[0].size(); pref = vector<vector<int>>(N+1,vector<int>(M+1,0)); row = col = pref; arr = a; for(int i = 0;i<N;i++){ for(int j = 0;j<M;j++){ pref[i+1][j+1] = arr[i][j]; } } for(int i = 1;i<=N;i++){ for(int j = 1;j<=M;j++){ pref[i][j] += pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]; } } ll ans = 0; for(int i = 0;i<N;i++){ for(int j = 0;j<M;j++){ if(arr[i][j]){ row[i][j] = col[i][j] = 0; continue; } if(i)col[i][j] = col[i-1][j]+1; else col[i][j] = 1; if(j)row[i][j] = row[i][j-1]+1; else row[i][j] = 1; } } /* cerr<<"ROW: "<<endl; for(int i = 0;i<N;i++){ for(int j = 0;j<M;j++)cerr<<row[i][j]<<' ';cerr<<endl; }cerr<<endl; cerr<<"COL: "<<endl; for(int i = 0;i<N;i++){ for(int j = 0;j<M;j++)cerr<<col[i][j]<<' ';cerr<<endl; }cerr<<endl; */ for(int i = 1;i+1<N;i++){ for(int j = 1;j+1<M;j++){ if(!row[i][j])continue; int h = col[i][j],w = row[i][j]; if(i<h||j<w)continue; /* if(sum(i-h+1,i,j-w+1,j) == 0){ cerr<<"ZERO: "<<i<<' '<<j<<":"<<h<<' '<<w<<endl; } */ if(sum(i-h+1,i,j+1,j+1) == sum(i-h+1,i,j-w,j-w) && sum(i-h+1,i,j+1,j+1) == h&& sum(i-h,i-h,j-w+1,j) == sum(i+1,i+1,j-w+1,j)&&sum(i-h,i-h,j-w+1,j) == w&& sum(i-h+1,i,j-w+1,j) == 0)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...