제출 #209946

#제출 시각아이디문제언어결과실행 시간메모리
209946SegtreeRectangles (IOI19_rect)C++14
13 / 100
554 ms258168 KiB
#include"rect.h" #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<set> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<ll,ll> P; typedef unordered_set<ll> uset; #define rep(i,n) for(int i=0;i<n;i++) #define rrep(i,n) for(int i=0;i<=n;i++) #define chmin(a,b) a=min(a,b) #define chmax(a,b) a=max(a,b) #define all(x) x.begin(),x.end() #pragma gcc optimize("O3") #pragma gcc optimize("unroll-loops") #pragma gcc target("avx2,see4") #define N 2510 ll h,w,d[N][N]; ll rui[N][N]; ll qry(ll x1,ll x2,ll y1,ll y2){//全て0のとき0、1のとき1、混在しているとき2 x2++,y2++; ll res=rui[x2][y2]+rui[x1][y1]-rui[x2][y1]-rui[x1][y2]; if(res==0)return 0; if(res==(x2-x1)*(y2-y1))return 1; return 2; } ll nx[N][N],ny[N][N]; ll count_rectangles(vector<vector<int> >A){ h=A.size(),w=A[0].size(); rep(i,h)rep(j,w)d[i][j]=A[i][j]; rep(i,h+1)rep(j,w+1)rui[i][j]=0; rep(i,h)rep(j,w)rui[i+1][j+1]=A[i][j]; rep(i,h+1)rep(j,w){ rui[i][j+1]+=rui[i][j]; } rep(j,w+1)rep(i,h){ rui[i+1][j]+=rui[i][j]; } rep(i,h+1)rep(j,w+1)nx[i][j]=ny[i][j]=1e9; rep(i,h){ for(int j=w-1;j>=0;j--)nx[i][j]=(A[i][j]==1?j:nx[i][j+1]); } rep(j,w){ for(int i=h-1;i>=0;i--)ny[i][j]=(A[i][j]==1?i:ny[i+1][j]); } ll ans=0; for(int i=1;i<h-1;i++)for(int j=1;j<w-1;j++){ if(A[i][j]==1)continue; int x1=i,x2=ny[i][j]-1; if(x2>h-2)continue; int y1=j,y2=nx[i][j]-1; if(y2>w-2)continue; //cerr<<x1<<" "<<x2<<" "<<y1<<" "<<y2<<endl; bool ok=qry(x1,x2,y1,y2)==0; ok&=qry(x1-1,x1-1,y1,y2)==1; ok&=qry(x2+1,x2+1,y1,y2)==1; ok&=qry(x1,x2,y1-1,y1-1)==1; ok&=qry(x1,x2,y2+1,y2+1)==1; ans+=ok; } return ans; }/* int main(){ ll h,w; cin>>h>>w; vector<vector<int> >a(h); rep(i,h){ rep(j,w){ ll val;cin>>val; a[i].push_back(val); } } cout<<count_rectangles(a)<<endl; }*/

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp:17:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("O3")
 
rect.cpp:18:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("unroll-loops")
 
rect.cpp:19:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
 #pragma gcc target("avx2,see4")
#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...