제출 #209933

#제출 시각아이디문제언어결과실행 시간메모리
209933SegtreeRectangles (IOI19_rect)C++14
10 / 100
93 ms121860 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 2500 #define H 3 int h,w,d[N][N]; namespace rangemax{ int dat1[H][N][N];//dat1[x][y1][y2] int dat2[N][H][H];//dat2[y][x1][x2] ll max_x(ll x,ll y1,ll y2){ return dat1[x][y1][y2]; } ll max_y(ll y,ll x1,ll x2){ return dat2[y][x1][x2]; } void init(){ rep(i,h){ rep(l,w){ dat1[i][l][l]=d[i][l]; for(int r=l+1;r<w;r++){ dat1[i][l][r]=max(dat1[i][l][r-1],d[i][r]); } } } rep(i,w){ rep(l,h){ dat2[i][l][l]=d[l][i]; for(int r=l+1;r<h;r++){ dat2[i][l][r]=max(dat2[i][l][r-1],d[r][i]); } } } } }; namespace rangejudge{ int dat1[H][N][N];//dat1[x][y1][y2] int dat2[N][H][H];//dat2[y][x1][x2] void init(){ rep(i,h){ for(int l=0;l<w;l++)for(int r=l;r<w;r++){ dat1[i][l][r]=rangemax::max_x(i,l,r)>=min(d[i][l-1],d[i][r+1]); } } for(int l=0;l<w;l++)for(int r=l;r<w;r++){ for(int i=1;i<h;i++)dat1[i][l][r]+=dat1[i-1][l][r]; } rep(i,w){ for(int l=0;l<h;l++)for(int r=l;r<h;r++){ dat2[i][l][r]=rangemax::max_y(i,l,r)>=min(d[l-1][i],d[r+1][i]); } } for(int l=0;l<h;l++)for(int r=l;r<h;r++){ for(int i=1;i<w;i++)dat2[i][l][r]+=dat2[i-1][l][r]; } } bool solve(ll x1,ll x2,ll y1,ll y2){ if(dat1[x2][y1][y2]-dat1[x1-1][y1][y2]>0)return 0; if(dat2[y2][x1][x2]-dat2[y1-1][x1][x2]>0)return 0; return 1; } }; 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]; rangemax::init(); rangejudge::init(); ll ans=0; for(int x1=1;x1<h-1;x1++)for(int x2=x1;x2<h-1;x2++) for(int y1=1;y1<w-1;y1++)for(int y2=y1;y2<w-1;y2++){ ans+=rangejudge::solve(x1,x2,y1,y2); } 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...