# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
169800 | 2019-12-22T22:26:13 Z | arthur_nascimento | Rectangles (IOI19_rect) | C++14 | 5000 ms | 86008 KB |
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define debug #define ll long long #define maxn 2525 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(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; } 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; } 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]; return go(0,m-1); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 504 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 2 ms | 504 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 380 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 504 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 256 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 2 ms | 256 KB | Output is correct |
18 | Correct | 2 ms | 376 KB | Output is correct |
19 | Correct | 2 ms | 504 KB | Output is correct |
20 | Correct | 2 ms | 376 KB | Output is correct |
21 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 504 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 2 ms | 504 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 380 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 504 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 256 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 33 ms | 760 KB | Output is correct |
18 | Correct | 33 ms | 808 KB | Output is correct |
19 | Correct | 33 ms | 760 KB | Output is correct |
20 | Correct | 3 ms | 760 KB | Output is correct |
21 | Correct | 5 ms | 700 KB | Output is correct |
22 | Correct | 5 ms | 760 KB | Output is correct |
23 | Correct | 5 ms | 760 KB | Output is correct |
24 | Correct | 3 ms | 760 KB | Output is correct |
25 | Correct | 2 ms | 256 KB | Output is correct |
26 | Correct | 2 ms | 376 KB | Output is correct |
27 | Correct | 2 ms | 504 KB | Output is correct |
28 | Correct | 2 ms | 376 KB | Output is correct |
29 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 504 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 2 ms | 504 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 380 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 504 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 256 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 33 ms | 760 KB | Output is correct |
18 | Correct | 33 ms | 808 KB | Output is correct |
19 | Correct | 33 ms | 760 KB | Output is correct |
20 | Correct | 3 ms | 760 KB | Output is correct |
21 | Correct | 5 ms | 700 KB | Output is correct |
22 | Correct | 5 ms | 760 KB | Output is correct |
23 | Correct | 5 ms | 760 KB | Output is correct |
24 | Correct | 3 ms | 760 KB | Output is correct |
25 | Correct | 1193 ms | 1820 KB | Output is correct |
26 | Correct | 1196 ms | 1860 KB | Output is correct |
27 | Correct | 1200 ms | 2040 KB | Output is correct |
28 | Correct | 12 ms | 1656 KB | Output is correct |
29 | Correct | 23 ms | 1784 KB | Output is correct |
30 | Correct | 23 ms | 1912 KB | Output is correct |
31 | Correct | 24 ms | 1928 KB | Output is correct |
32 | Correct | 24 ms | 1912 KB | Output is correct |
33 | Correct | 2 ms | 256 KB | Output is correct |
34 | Correct | 2 ms | 376 KB | Output is correct |
35 | Correct | 2 ms | 504 KB | Output is correct |
36 | Correct | 2 ms | 376 KB | Output is correct |
37 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 504 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 2 ms | 504 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 380 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 504 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 256 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 33 ms | 760 KB | Output is correct |
18 | Correct | 33 ms | 808 KB | Output is correct |
19 | Correct | 33 ms | 760 KB | Output is correct |
20 | Correct | 3 ms | 760 KB | Output is correct |
21 | Correct | 5 ms | 700 KB | Output is correct |
22 | Correct | 5 ms | 760 KB | Output is correct |
23 | Correct | 5 ms | 760 KB | Output is correct |
24 | Correct | 3 ms | 760 KB | Output is correct |
25 | Correct | 1193 ms | 1820 KB | Output is correct |
26 | Correct | 1196 ms | 1860 KB | Output is correct |
27 | Correct | 1200 ms | 2040 KB | Output is correct |
28 | Correct | 12 ms | 1656 KB | Output is correct |
29 | Correct | 23 ms | 1784 KB | Output is correct |
30 | Correct | 23 ms | 1912 KB | Output is correct |
31 | Correct | 24 ms | 1928 KB | Output is correct |
32 | Correct | 24 ms | 1912 KB | Output is correct |
33 | Execution timed out | 5014 ms | 12152 KB | Time limit exceeded |
34 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 248 KB | Output is correct |
2 | Correct | 15 ms | 504 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 3 ms | 504 KB | Output is correct |
6 | Correct | 3 ms | 504 KB | Output is correct |
7 | Correct | 3 ms | 632 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 500 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 1363 ms | 40696 KB | Output is correct |
3 | Execution timed out | 5016 ms | 86008 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 504 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 2 ms | 504 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 380 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 504 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 256 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 33 ms | 760 KB | Output is correct |
18 | Correct | 33 ms | 808 KB | Output is correct |
19 | Correct | 33 ms | 760 KB | Output is correct |
20 | Correct | 3 ms | 760 KB | Output is correct |
21 | Correct | 5 ms | 700 KB | Output is correct |
22 | Correct | 5 ms | 760 KB | Output is correct |
23 | Correct | 5 ms | 760 KB | Output is correct |
24 | Correct | 3 ms | 760 KB | Output is correct |
25 | Correct | 1193 ms | 1820 KB | Output is correct |
26 | Correct | 1196 ms | 1860 KB | Output is correct |
27 | Correct | 1200 ms | 2040 KB | Output is correct |
28 | Correct | 12 ms | 1656 KB | Output is correct |
29 | Correct | 23 ms | 1784 KB | Output is correct |
30 | Correct | 23 ms | 1912 KB | Output is correct |
31 | Correct | 24 ms | 1928 KB | Output is correct |
32 | Correct | 24 ms | 1912 KB | Output is correct |
33 | Execution timed out | 5014 ms | 12152 KB | Time limit exceeded |
34 | Halted | 0 ms | 0 KB | - |