제출 #169803

#제출 시각아이디문제언어결과실행 시간메모리
169803arthur_nascimentoRectangles (IOI19_rect)C++14
37 / 100
5122 ms1048580 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define debug #define ll long long #define maxn 2525 int lg[maxn]; struct rmq { int len; int arr[maxn]; int mx[13][maxn]; int id[13][maxn]; void build(){ lg[1] = 0; for(int i=2;i<=len;i++) lg[i] = lg[i-1] + (i == (i&-i)); for(int i=0;i<len;i++){ mx[0][i] = arr[i]; id[0][i] = i; } for(int i=1;i<13;i++) for(int j=0;j<len;j++){ int ot = min(len-1, j + ( 1 << (i-1))); int A = mx[i-1][j], B = mx[i-1][ot]; if(A > B){ mx[i][j] = A; id[i][j] = id[i-1][j]; } else { mx[i][j] = B; id[i][j] = id[i-1][ot]; } } } int pos(int x,int y){ int l = lg[y-x+1]; int A = mx[l][x], B = mx[l][y-(1<<l)+1]; if(A > B) return id[l][x]; else return id[l][y-(1<<l)+1]; } int val(int x,int y){ int l = lg[y-x+1]; int A = mx[l][x], B = mx[l][y-(1<<l)+1]; return max(A,B); } } RMQ[2][maxn]; int M[maxn][maxn]; int n,m; int line(int i,int yi,int yf){ int r = 1; for(int j=yi;j<=yf;j++) if(M[i][j] >= M[i][yi-1] || M[i][j] >= M[i][yf+1]) r = 0; return r; } int column(int j,int xi,int xf){ int r = 1; for(int i=xi;i<=xf;i++) if(M[i][j] >= M[xi-1][j] || M[i][j] >= M[xf+1][j]) r = 0; return r; } int check(int xi,int xf,int yi,int yf){ int r = 1; assert(xi >= 1 && xf <= n-2 && yi >= 1 && yf <= m-2); for(int i=xi;i<=xf;i++) r *= line(i,yi,yf); for(int j=yi;j<=yf;j++) r *= column(j,xi,xf); if(r) debug("achou x:%d~%d y: %d~%d\n",xi,xf,yi,yf); return r; } ll go4(int xi,int xf,int yi,int yf,int ym){ if(xi > xf || yi > yf) return 0; if(yi > ym || yf < ym) return 0; debug("oi4\n"); ll ans = check(xi,xf,yi,yf); int mx = -1, id = -1; for(int i=yi;i<=yf;i++) if(M[xi][i] > mx){ mx = M[xi][i]; id = i; } ans += go4(xi,xf,yi,id-1,ym) + go4(xi,xf,id+1,yf,ym); debug("tchau 4\n"); return ans; } ll go3(int xi,int xf,int yi,int yf,int ym){ if(xi == 0 || xf == n-1) return 0; if(xi > xf) return 0; int A = ym, B = ym; debug("oi x: %d~%d y: %d~%d quebra A ? B ?\n",xi,xf,yi,yf); while(1){ A--; if(A == 0 || A < yi) break; debug("A %d\n",A); int ok = 1; //for(int i=xi;i<=xf;i++) // if(M[i][A] >= M[xi-1][A] || M[i][A] >= M[xf+1][A]) ok = 0; if(RMQ[1][A].val(xi,xf) >= min(M[xi-1][A],M[xf+1][A])) ok = 0; if(ok == 0) break; } A++; while(1){ B++; if(B == m-1 || B > yf) break; int ok = 1; //for(int i=xi;i<=xf;i++) // if(M[i][B] >= M[xi-1][B] || M[i][B] >= M[xf+1][B]) ok = 0; if(RMQ[1][B].val(xi,xf) >= min(M[xi-1][B],M[xf+1][B])) ok = 0; } B--; debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B); return go4(xi,xf,A,B,ym); } ll go2(int xi,int xf,int yi,int yf,int ym){ if(xi > xf) return 0; if(yi > yf) return 0; if(ym == 0 || ym == m-1) return 0; debug("go2 x %d~%d y %d~%d\n",xi,xf,yi,yf); int mx = -1, id = -1; /*for(int i=xi;i<=xf;i++) if(M[i][ym] > mx){ mx = M[i][ym]; id = i; }*/ id = RMQ[1][ym].pos(xi,xf); ll ans = go3(xi,id-1,yi,yf,ym) + go3(id+1,xf,yi,yf,ym) + go2(xi,id-1,yi,yf,ym) + go2(id+1,xf,yi,yf,ym); return ans; } ll go(int yi,int yf){ if(yi > yf) return 0; int ym = (yi+yf)/2; debug("oi\n"); ll ans = go(yi,ym-1) + go(ym+1,yf) + go2(0,n-1,yi,yf,ym); return ans; } long long count_rectangles(std::vector<std::vector<int> > a) { n = a.size(); m = a[0].size(); for(int i=0;i<n;i++) for(int j=0;j<m;j++) M[i][j] = a[i][j]; for(int i=0;i<n;i++){ RMQ[0][i].len = m; for(int j=0;j<m;j++) RMQ[0][i].arr[j] = M[i][j]; RMQ[0][i].build(); } for(int j=0;j<m;j++){ RMQ[1][j].len = n; for(int i=0;i<n;i++) RMQ[1][j].arr[i] = M[i][j]; RMQ[1][j].build(); } return go(0,m-1); }

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

rect.cpp: In function 'int check(int, int, int, int)':
rect.cpp:86:36: warning: left operand of comma operator has no effect [-Wunused-value]
   debug("achou x:%d~%d y: %d~%d\n",xi,xf,yi,yf);
                                    ^~
rect.cpp:86:39: warning: right operand of comma operator has no effect [-Wunused-value]
   debug("achou x:%d~%d y: %d~%d\n",xi,xf,yi,yf);
                                       ^~
rect.cpp:86:42: warning: right operand of comma operator has no effect [-Wunused-value]
   debug("achou x:%d~%d y: %d~%d\n",xi,xf,yi,yf);
                                          ^~
rect.cpp:86:45: warning: right operand of comma operator has no effect [-Wunused-value]
   debug("achou x:%d~%d y: %d~%d\n",xi,xf,yi,yf);
                                             ^~
rect.cpp: In function 'long long int go4(int, int, int, int, int)':
rect.cpp:94:16: warning: statement has no effect [-Wunused-value]
  debug("oi4\n");
                ^
rect.cpp:106:20: warning: statement has no effect [-Wunused-value]
  debug("tchau 4\n");
                    ^
rect.cpp: In function 'long long int go3(int, int, int, int, int)':
rect.cpp:118:48: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("oi x: %d~%d y: %d~%d quebra A ? B ?\n",xi,xf,yi,yf);
                                                ^~
rect.cpp:118:51: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("oi x: %d~%d y: %d~%d quebra A ? B ?\n",xi,xf,yi,yf);
                                                   ^~
rect.cpp:118:54: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("oi x: %d~%d y: %d~%d quebra A ? B ?\n",xi,xf,yi,yf);
                                                      ^~
rect.cpp:118:57: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("oi x: %d~%d y: %d~%d quebra A ? B ?\n",xi,xf,yi,yf);
                                                         ^~
rect.cpp:124:18: warning: left operand of comma operator has no effect [-Wunused-value]
   debug("A %d\n",A);
                  ^
rect.cpp:136:7: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   int ok = 1;
       ^~
rect.cpp:143:51: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
                                                   ^~
rect.cpp:143:54: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
                                                      ^~
rect.cpp:143:57: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
                                                         ^~
rect.cpp:143:60: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
                                                            ^~
rect.cpp:143:63: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
                                                               ^
rect.cpp:143:65: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
                                                                 ^
rect.cpp: In function 'long long int go2(int, int, int, int, int)':
rect.cpp:154:32: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("go2 x %d~%d y %d~%d\n",xi,xf,yi,yf);
                                ^~
rect.cpp:154:35: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go2 x %d~%d y %d~%d\n",xi,xf,yi,yf);
                                   ^~
rect.cpp:154:38: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go2 x %d~%d y %d~%d\n",xi,xf,yi,yf);
                                      ^~
rect.cpp:154:41: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go2 x %d~%d y %d~%d\n",xi,xf,yi,yf);
                                         ^~
rect.cpp:156:6: warning: unused variable 'mx' [-Wunused-variable]
  int mx = -1, id = -1;
      ^~
rect.cpp: In function 'long long int go(int, int)':
rect.cpp:179:15: warning: statement has no effect [-Wunused-value]
  debug("oi\n");
               ^
#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...