# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
169844 | 2019-12-23T00:41:08 Z | arthur_nascimento | Rectangles (IOI19_rect) | C++14 | 5000 ms | 809864 KB |
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define debug #define ll long long #define maxn 2505 int lg[maxn]; struct rmq { int len; int arr[maxn]; short id[13][maxn]; inline int mx(int i,int j){ return arr[id[i][j]]; } int l,A,B; 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]; } } } inline int pos(int x,int y){ l = lg[y-x+1]; 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]; } inline int val(int x,int y){ l = lg[y-x+1]; A = mx(l,x), B = mx(l,y-(1<<l)+1); return max(A,B); } } RMQ[4][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; } inline int check(int xi,int xf,int yi,int yf){ //for(int i=xi;i<=xf;i++) // if( RMQ[0][i].val(yi,yf) >= min( M[i][yi-1],M[i][yf+1])) return 0; // min if( -RMQ[2][yi-1].val(xi,xf) <= yf) return 0; if(RMQ[3][yf+1].val(xi,xf) >= yi) return 0; //for(int j=yi;j<=yf;j++) // if( RMQ[1][j].val(xi,xf) >= min( M[xi-1][j],M[xf+1][j])) return 0; return 1; //return 1; 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; }*/ id = RMQ[0][xi].pos(yi,yf); 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); if(RMQ[1][ym].val(xi,xf) >= min(M[xi-1][ym],M[xf+1][ym])) return 0; 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(ok == 0) break; } 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++){ stack<int> S; for(int j=m-1;j>=0;j--){ while(S.size() > 0 && M[i][j] > M[i][S.top()] ) S.pop(); if(S.size() == 0) RMQ[2][j].arr[i] = m+1; else RMQ[2][j].arr[i] = S.top(); S.push(j); } while(S.size() > 0) S.pop(); for(int j=0;j<m;j++){ while(S.size() > 0 && M[i][j] > M[i][S.top()] ) S.pop(); if(S.size() == 0) RMQ[3][j].arr[i] = -1; else RMQ[3][j].arr[i] = S.top(); S.push(j); } } for(int i=0;i<m;i++){ RMQ[2][i].len = n; RMQ[3][i].len = n; for(int j=0;j<n;j++) RMQ[2][i].arr[j] *= -1; RMQ[2][i].build(); RMQ[3][i].build(); } 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); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1528 KB | Output is correct |
2 | Correct | 7 ms | 7288 KB | Output is correct |
3 | Correct | 7 ms | 7288 KB | Output is correct |
4 | Correct | 7 ms | 7288 KB | Output is correct |
5 | Correct | 7 ms | 7288 KB | Output is correct |
6 | Correct | 7 ms | 7288 KB | Output is correct |
7 | Correct | 5 ms | 4344 KB | Output is correct |
8 | Correct | 6 ms | 6136 KB | Output is correct |
9 | Correct | 7 ms | 7288 KB | Output is correct |
10 | Correct | 7 ms | 7288 KB | Output is correct |
11 | Correct | 7 ms | 7288 KB | Output is correct |
12 | Correct | 7 ms | 7292 KB | Output is correct |
13 | Correct | 2 ms | 504 KB | Output is correct |
14 | Correct | 2 ms | 1272 KB | Output is correct |
15 | Correct | 3 ms | 2424 KB | Output is correct |
16 | Correct | 2 ms | 1016 KB | Output is correct |
17 | Correct | 2 ms | 632 KB | Output is correct |
18 | Correct | 3 ms | 1272 KB | Output is correct |
19 | Correct | 7 ms | 7288 KB | Output is correct |
20 | Correct | 5 ms | 4700 KB | Output is correct |
21 | Correct | 3 ms | 1272 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1528 KB | Output is correct |
2 | Correct | 7 ms | 7288 KB | Output is correct |
3 | Correct | 7 ms | 7288 KB | Output is correct |
4 | Correct | 7 ms | 7288 KB | Output is correct |
5 | Correct | 7 ms | 7288 KB | Output is correct |
6 | Correct | 7 ms | 7288 KB | Output is correct |
7 | Correct | 5 ms | 4344 KB | Output is correct |
8 | Correct | 6 ms | 6136 KB | Output is correct |
9 | Correct | 7 ms | 7288 KB | Output is correct |
10 | Correct | 7 ms | 7288 KB | Output is correct |
11 | Correct | 7 ms | 7288 KB | Output is correct |
12 | Correct | 7 ms | 7292 KB | Output is correct |
13 | Correct | 2 ms | 504 KB | Output is correct |
14 | Correct | 2 ms | 1272 KB | Output is correct |
15 | Correct | 3 ms | 2424 KB | Output is correct |
16 | Correct | 2 ms | 1016 KB | Output is correct |
17 | Correct | 19 ms | 19448 KB | Output is correct |
18 | Correct | 19 ms | 19448 KB | Output is correct |
19 | Correct | 19 ms | 19448 KB | Output is correct |
20 | Correct | 17 ms | 19448 KB | Output is correct |
21 | Correct | 18 ms | 19320 KB | Output is correct |
22 | Correct | 18 ms | 19192 KB | Output is correct |
23 | Correct | 18 ms | 19448 KB | Output is correct |
24 | Correct | 12 ms | 12300 KB | Output is correct |
25 | Correct | 2 ms | 632 KB | Output is correct |
26 | Correct | 3 ms | 1272 KB | Output is correct |
27 | Correct | 7 ms | 7288 KB | Output is correct |
28 | Correct | 5 ms | 4700 KB | Output is correct |
29 | Correct | 3 ms | 1272 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1528 KB | Output is correct |
2 | Correct | 7 ms | 7288 KB | Output is correct |
3 | Correct | 7 ms | 7288 KB | Output is correct |
4 | Correct | 7 ms | 7288 KB | Output is correct |
5 | Correct | 7 ms | 7288 KB | Output is correct |
6 | Correct | 7 ms | 7288 KB | Output is correct |
7 | Correct | 5 ms | 4344 KB | Output is correct |
8 | Correct | 6 ms | 6136 KB | Output is correct |
9 | Correct | 7 ms | 7288 KB | Output is correct |
10 | Correct | 7 ms | 7288 KB | Output is correct |
11 | Correct | 7 ms | 7288 KB | Output is correct |
12 | Correct | 7 ms | 7292 KB | Output is correct |
13 | Correct | 2 ms | 504 KB | Output is correct |
14 | Correct | 2 ms | 1272 KB | Output is correct |
15 | Correct | 3 ms | 2424 KB | Output is correct |
16 | Correct | 2 ms | 1016 KB | Output is correct |
17 | Correct | 19 ms | 19448 KB | Output is correct |
18 | Correct | 19 ms | 19448 KB | Output is correct |
19 | Correct | 19 ms | 19448 KB | Output is correct |
20 | Correct | 17 ms | 19448 KB | Output is correct |
21 | Correct | 18 ms | 19320 KB | Output is correct |
22 | Correct | 18 ms | 19192 KB | Output is correct |
23 | Correct | 18 ms | 19448 KB | Output is correct |
24 | Correct | 12 ms | 12300 KB | Output is correct |
25 | Correct | 73 ms | 51192 KB | Output is correct |
26 | Correct | 74 ms | 51192 KB | Output is correct |
27 | Correct | 74 ms | 51196 KB | Output is correct |
28 | Correct | 63 ms | 51196 KB | Output is correct |
29 | Correct | 55 ms | 51324 KB | Output is correct |
30 | Correct | 55 ms | 51192 KB | Output is correct |
31 | Correct | 55 ms | 51164 KB | Output is correct |
32 | Correct | 54 ms | 50776 KB | Output is correct |
33 | Correct | 2 ms | 632 KB | Output is correct |
34 | Correct | 3 ms | 1272 KB | Output is correct |
35 | Correct | 7 ms | 7288 KB | Output is correct |
36 | Correct | 5 ms | 4700 KB | Output is correct |
37 | Correct | 3 ms | 1272 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1528 KB | Output is correct |
2 | Correct | 7 ms | 7288 KB | Output is correct |
3 | Correct | 7 ms | 7288 KB | Output is correct |
4 | Correct | 7 ms | 7288 KB | Output is correct |
5 | Correct | 7 ms | 7288 KB | Output is correct |
6 | Correct | 7 ms | 7288 KB | Output is correct |
7 | Correct | 5 ms | 4344 KB | Output is correct |
8 | Correct | 6 ms | 6136 KB | Output is correct |
9 | Correct | 7 ms | 7288 KB | Output is correct |
10 | Correct | 7 ms | 7288 KB | Output is correct |
11 | Correct | 7 ms | 7288 KB | Output is correct |
12 | Correct | 7 ms | 7292 KB | Output is correct |
13 | Correct | 2 ms | 504 KB | Output is correct |
14 | Correct | 2 ms | 1272 KB | Output is correct |
15 | Correct | 3 ms | 2424 KB | Output is correct |
16 | Correct | 2 ms | 1016 KB | Output is correct |
17 | Correct | 19 ms | 19448 KB | Output is correct |
18 | Correct | 19 ms | 19448 KB | Output is correct |
19 | Correct | 19 ms | 19448 KB | Output is correct |
20 | Correct | 17 ms | 19448 KB | Output is correct |
21 | Correct | 18 ms | 19320 KB | Output is correct |
22 | Correct | 18 ms | 19192 KB | Output is correct |
23 | Correct | 18 ms | 19448 KB | Output is correct |
24 | Correct | 12 ms | 12300 KB | Output is correct |
25 | Correct | 73 ms | 51192 KB | Output is correct |
26 | Correct | 74 ms | 51192 KB | Output is correct |
27 | Correct | 74 ms | 51196 KB | Output is correct |
28 | Correct | 63 ms | 51196 KB | Output is correct |
29 | Correct | 55 ms | 51324 KB | Output is correct |
30 | Correct | 55 ms | 51192 KB | Output is correct |
31 | Correct | 55 ms | 51164 KB | Output is correct |
32 | Correct | 54 ms | 50776 KB | Output is correct |
33 | Correct | 331 ms | 206396 KB | Output is correct |
34 | Correct | 342 ms | 206544 KB | Output is correct |
35 | Correct | 310 ms | 206556 KB | Output is correct |
36 | Correct | 337 ms | 206508 KB | Output is correct |
37 | Correct | 1690 ms | 206456 KB | Output is correct |
38 | Correct | 1655 ms | 206328 KB | Output is correct |
39 | Correct | 1663 ms | 206328 KB | Output is correct |
40 | Correct | 1462 ms | 202232 KB | Output is correct |
41 | Correct | 294 ms | 206496 KB | Output is correct |
42 | Correct | 309 ms | 206452 KB | Output is correct |
43 | Correct | 367 ms | 206328 KB | Output is correct |
44 | Correct | 374 ms | 206328 KB | Output is correct |
45 | Correct | 208 ms | 126728 KB | Output is correct |
46 | Correct | 231 ms | 168796 KB | Output is correct |
47 | Correct | 389 ms | 206644 KB | Output is correct |
48 | Correct | 378 ms | 206508 KB | Output is correct |
49 | Correct | 2 ms | 632 KB | Output is correct |
50 | Correct | 3 ms | 1272 KB | Output is correct |
51 | Correct | 7 ms | 7288 KB | Output is correct |
52 | Correct | 5 ms | 4700 KB | Output is correct |
53 | Correct | 3 ms | 1272 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 317 ms | 422368 KB | Output is correct |
2 | Correct | 274 ms | 358752 KB | Output is correct |
3 | Correct | 320 ms | 422368 KB | Output is correct |
4 | Correct | 2 ms | 760 KB | Output is correct |
5 | Correct | 321 ms | 422392 KB | Output is correct |
6 | Correct | 320 ms | 422344 KB | Output is correct |
7 | Correct | 317 ms | 422520 KB | Output is correct |
8 | Correct | 318 ms | 422296 KB | Output is correct |
9 | Correct | 348 ms | 422364 KB | Output is correct |
10 | Correct | 336 ms | 421624 KB | Output is correct |
11 | Correct | 358 ms | 422128 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2552 KB | Output is correct |
2 | Correct | 1457 ms | 631380 KB | Output is correct |
3 | Correct | 2708 ms | 808440 KB | Output is correct |
4 | Correct | 2650 ms | 809700 KB | Output is correct |
5 | Correct | 2664 ms | 809824 KB | Output is correct |
6 | Correct | 1239 ms | 671984 KB | Output is correct |
7 | Correct | 2072 ms | 772588 KB | Output is correct |
8 | Correct | 2331 ms | 809856 KB | Output is correct |
9 | Correct | 2 ms | 632 KB | Output is correct |
10 | Correct | 3 ms | 1272 KB | Output is correct |
11 | Correct | 7 ms | 7288 KB | Output is correct |
12 | Correct | 5 ms | 4700 KB | Output is correct |
13 | Correct | 3 ms | 1272 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1528 KB | Output is correct |
2 | Correct | 7 ms | 7288 KB | Output is correct |
3 | Correct | 7 ms | 7288 KB | Output is correct |
4 | Correct | 7 ms | 7288 KB | Output is correct |
5 | Correct | 7 ms | 7288 KB | Output is correct |
6 | Correct | 7 ms | 7288 KB | Output is correct |
7 | Correct | 5 ms | 4344 KB | Output is correct |
8 | Correct | 6 ms | 6136 KB | Output is correct |
9 | Correct | 7 ms | 7288 KB | Output is correct |
10 | Correct | 7 ms | 7288 KB | Output is correct |
11 | Correct | 7 ms | 7288 KB | Output is correct |
12 | Correct | 7 ms | 7292 KB | Output is correct |
13 | Correct | 2 ms | 504 KB | Output is correct |
14 | Correct | 2 ms | 1272 KB | Output is correct |
15 | Correct | 3 ms | 2424 KB | Output is correct |
16 | Correct | 2 ms | 1016 KB | Output is correct |
17 | Correct | 19 ms | 19448 KB | Output is correct |
18 | Correct | 19 ms | 19448 KB | Output is correct |
19 | Correct | 19 ms | 19448 KB | Output is correct |
20 | Correct | 17 ms | 19448 KB | Output is correct |
21 | Correct | 18 ms | 19320 KB | Output is correct |
22 | Correct | 18 ms | 19192 KB | Output is correct |
23 | Correct | 18 ms | 19448 KB | Output is correct |
24 | Correct | 12 ms | 12300 KB | Output is correct |
25 | Correct | 73 ms | 51192 KB | Output is correct |
26 | Correct | 74 ms | 51192 KB | Output is correct |
27 | Correct | 74 ms | 51196 KB | Output is correct |
28 | Correct | 63 ms | 51196 KB | Output is correct |
29 | Correct | 55 ms | 51324 KB | Output is correct |
30 | Correct | 55 ms | 51192 KB | Output is correct |
31 | Correct | 55 ms | 51164 KB | Output is correct |
32 | Correct | 54 ms | 50776 KB | Output is correct |
33 | Correct | 331 ms | 206396 KB | Output is correct |
34 | Correct | 342 ms | 206544 KB | Output is correct |
35 | Correct | 310 ms | 206556 KB | Output is correct |
36 | Correct | 337 ms | 206508 KB | Output is correct |
37 | Correct | 1690 ms | 206456 KB | Output is correct |
38 | Correct | 1655 ms | 206328 KB | Output is correct |
39 | Correct | 1663 ms | 206328 KB | Output is correct |
40 | Correct | 1462 ms | 202232 KB | Output is correct |
41 | Correct | 294 ms | 206496 KB | Output is correct |
42 | Correct | 309 ms | 206452 KB | Output is correct |
43 | Correct | 367 ms | 206328 KB | Output is correct |
44 | Correct | 374 ms | 206328 KB | Output is correct |
45 | Correct | 208 ms | 126728 KB | Output is correct |
46 | Correct | 231 ms | 168796 KB | Output is correct |
47 | Correct | 389 ms | 206644 KB | Output is correct |
48 | Correct | 378 ms | 206508 KB | Output is correct |
49 | Correct | 317 ms | 422368 KB | Output is correct |
50 | Correct | 274 ms | 358752 KB | Output is correct |
51 | Correct | 320 ms | 422368 KB | Output is correct |
52 | Correct | 2 ms | 760 KB | Output is correct |
53 | Correct | 321 ms | 422392 KB | Output is correct |
54 | Correct | 320 ms | 422344 KB | Output is correct |
55 | Correct | 317 ms | 422520 KB | Output is correct |
56 | Correct | 318 ms | 422296 KB | Output is correct |
57 | Correct | 348 ms | 422364 KB | Output is correct |
58 | Correct | 336 ms | 421624 KB | Output is correct |
59 | Correct | 358 ms | 422128 KB | Output is correct |
60 | Correct | 4 ms | 2552 KB | Output is correct |
61 | Correct | 1457 ms | 631380 KB | Output is correct |
62 | Correct | 2708 ms | 808440 KB | Output is correct |
63 | Correct | 2650 ms | 809700 KB | Output is correct |
64 | Correct | 2664 ms | 809824 KB | Output is correct |
65 | Correct | 1239 ms | 671984 KB | Output is correct |
66 | Correct | 2072 ms | 772588 KB | Output is correct |
67 | Correct | 2331 ms | 809856 KB | Output is correct |
68 | Execution timed out | 5076 ms | 809864 KB | Time limit exceeded |
69 | Halted | 0 ms | 0 KB | - |