# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
143758 |
2019-08-15T03:16:44 Z |
ondrah |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
636164 KB |
#include "rect.h"
#include <string.h>
#include <algorithm>
using namespace std;
#define REP(A, B) for(int (A)=0;(A)<(B); (A)++)
using ll = long long;
int rowMax[12][2555][2555]; //row,c1,c1+2^k
int colMax[12][2555][2555]; //
inline int getRowMax(int r, int c1, int c2) {
int d = (c2-c1) ? 31 - __builtin_clz(c2-c1) : 0;
return max(rowMax[d][r][c1], rowMax[d][r][c2-(1<<d)+1]);
}
inline int getColMax(int c, int r1, int r2) {
int d = (r2-r1) ? 31 - __builtin_clz(r2-r1) : 0;
return max(colMax[d][r1][c], colMax[d][r2-(1<<d)+1][c]);
}
long long count_rectangles(std::vector<std::vector<int> > a) {
memset(rowMax,-1,sizeof(rowMax));
memset(colMax, -1, sizeof(colMax));
int n = a.size();
int m = a[0].size();
REP(i, n) {
REP(j, m) rowMax[0][i][j] = colMax[0][i][j] = a[i][j];
}
for(int k = 1; k < 12; k++) {
REP(i, n) REP(j, m) {
int other = min(m-2, j+(1<<(k-1)));
rowMax[k][i][j] = max(rowMax[k-1][i][j], rowMax[k-1][i][other]);
}
}
for(int k = 1; k < 12; k++) {
REP(i, n) REP(j, m) {
int other = min(n-2, i+(1<<(k-1)));
colMax[k][i][j] = max(colMax[k-1][i][j], colMax[k-1][other][j]);
}
}
ll ans = 0;
for(int r1 = 1; r1 <= n-2; r1++) {
for(int c1 = 1; c1 <= m-2; c1++) {
int maxC2G = m-2;
for(int r2 = r1; r2 <= n-2; r2++) {
int maxC2 = min(m-2, maxC2G);
for(int c2 = c1; c2 <= maxC2; c2++) {
bool good = true;
bool breakc2 = false;
for(int rr = r1; rr <= r2; rr++) {
int rm = getRowMax(rr, c1, c2);
if(rm >= a[rr][c1-1]) {
//printf("r1=%d, r2=%d, c1=%d, c2=%d, ERR AT rr=%d\n", r1, r2, c1, c2, rr);
good = false;
breakc2 = true;
break;
}
if(rm >= a[rr][c2+1]) {
good = false;
break;
}
}
if(breakc2) break;
bool colGood = true;
for(int cc = c1; cc <= c2; cc++) {
int rm = getColMax(cc, r1, r2);
if(rm >= a[r1-1][cc]) {
good = false;
maxC2 = maxC2G = cc-1;
breakc2 = true;
break;
}
else if(rm >= a[r2+1][cc]) {
good = false;
maxC2 = cc-1;
breakc2 = true;
break;
}
}
if(breakc2) break;
if(good) {
ans++;
//printf("r1=%d, r2=%d, c1=%d, c2=%d\n", r1, r2, c1, c2);
}
}
}
}
}
return ans;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:63:11: warning: unused variable 'colGood' [-Wunused-variable]
bool colGood = true;
^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
506 ms |
613648 KB |
Output is correct |
2 |
Correct |
512 ms |
613548 KB |
Output is correct |
3 |
Correct |
520 ms |
613576 KB |
Output is correct |
4 |
Correct |
512 ms |
613596 KB |
Output is correct |
5 |
Correct |
507 ms |
613624 KB |
Output is correct |
6 |
Correct |
502 ms |
613476 KB |
Output is correct |
7 |
Correct |
505 ms |
613584 KB |
Output is correct |
8 |
Correct |
504 ms |
613504 KB |
Output is correct |
9 |
Correct |
505 ms |
613476 KB |
Output is correct |
10 |
Correct |
502 ms |
613612 KB |
Output is correct |
11 |
Correct |
523 ms |
613480 KB |
Output is correct |
12 |
Correct |
520 ms |
613680 KB |
Output is correct |
13 |
Correct |
500 ms |
613512 KB |
Output is correct |
14 |
Correct |
530 ms |
613532 KB |
Output is correct |
15 |
Correct |
507 ms |
613576 KB |
Output is correct |
16 |
Correct |
508 ms |
613624 KB |
Output is correct |
17 |
Correct |
505 ms |
613612 KB |
Output is correct |
18 |
Correct |
512 ms |
613636 KB |
Output is correct |
19 |
Correct |
504 ms |
613496 KB |
Output is correct |
20 |
Correct |
505 ms |
613520 KB |
Output is correct |
21 |
Correct |
502 ms |
613624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
506 ms |
613648 KB |
Output is correct |
2 |
Correct |
512 ms |
613548 KB |
Output is correct |
3 |
Correct |
520 ms |
613576 KB |
Output is correct |
4 |
Correct |
512 ms |
613596 KB |
Output is correct |
5 |
Correct |
507 ms |
613624 KB |
Output is correct |
6 |
Correct |
502 ms |
613476 KB |
Output is correct |
7 |
Correct |
505 ms |
613584 KB |
Output is correct |
8 |
Correct |
504 ms |
613504 KB |
Output is correct |
9 |
Correct |
505 ms |
613476 KB |
Output is correct |
10 |
Correct |
502 ms |
613612 KB |
Output is correct |
11 |
Correct |
523 ms |
613480 KB |
Output is correct |
12 |
Correct |
520 ms |
613680 KB |
Output is correct |
13 |
Correct |
500 ms |
613512 KB |
Output is correct |
14 |
Correct |
530 ms |
613532 KB |
Output is correct |
15 |
Correct |
507 ms |
613576 KB |
Output is correct |
16 |
Correct |
508 ms |
613624 KB |
Output is correct |
17 |
Correct |
552 ms |
613772 KB |
Output is correct |
18 |
Correct |
541 ms |
613624 KB |
Output is correct |
19 |
Correct |
602 ms |
613560 KB |
Output is correct |
20 |
Correct |
505 ms |
613652 KB |
Output is correct |
21 |
Correct |
513 ms |
613512 KB |
Output is correct |
22 |
Correct |
514 ms |
613696 KB |
Output is correct |
23 |
Correct |
508 ms |
613596 KB |
Output is correct |
24 |
Correct |
513 ms |
613604 KB |
Output is correct |
25 |
Correct |
505 ms |
613612 KB |
Output is correct |
26 |
Correct |
512 ms |
613636 KB |
Output is correct |
27 |
Correct |
504 ms |
613496 KB |
Output is correct |
28 |
Correct |
505 ms |
613520 KB |
Output is correct |
29 |
Correct |
502 ms |
613624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
506 ms |
613648 KB |
Output is correct |
2 |
Correct |
512 ms |
613548 KB |
Output is correct |
3 |
Correct |
520 ms |
613576 KB |
Output is correct |
4 |
Correct |
512 ms |
613596 KB |
Output is correct |
5 |
Correct |
507 ms |
613624 KB |
Output is correct |
6 |
Correct |
502 ms |
613476 KB |
Output is correct |
7 |
Correct |
505 ms |
613584 KB |
Output is correct |
8 |
Correct |
504 ms |
613504 KB |
Output is correct |
9 |
Correct |
505 ms |
613476 KB |
Output is correct |
10 |
Correct |
502 ms |
613612 KB |
Output is correct |
11 |
Correct |
523 ms |
613480 KB |
Output is correct |
12 |
Correct |
520 ms |
613680 KB |
Output is correct |
13 |
Correct |
500 ms |
613512 KB |
Output is correct |
14 |
Correct |
530 ms |
613532 KB |
Output is correct |
15 |
Correct |
507 ms |
613576 KB |
Output is correct |
16 |
Correct |
508 ms |
613624 KB |
Output is correct |
17 |
Correct |
552 ms |
613772 KB |
Output is correct |
18 |
Correct |
541 ms |
613624 KB |
Output is correct |
19 |
Correct |
602 ms |
613560 KB |
Output is correct |
20 |
Correct |
505 ms |
613652 KB |
Output is correct |
21 |
Correct |
513 ms |
613512 KB |
Output is correct |
22 |
Correct |
514 ms |
613696 KB |
Output is correct |
23 |
Correct |
508 ms |
613596 KB |
Output is correct |
24 |
Correct |
513 ms |
613604 KB |
Output is correct |
25 |
Correct |
1892 ms |
613872 KB |
Output is correct |
26 |
Correct |
1861 ms |
613880 KB |
Output is correct |
27 |
Correct |
1868 ms |
613880 KB |
Output is correct |
28 |
Correct |
530 ms |
613928 KB |
Output is correct |
29 |
Correct |
532 ms |
613868 KB |
Output is correct |
30 |
Correct |
544 ms |
613824 KB |
Output is correct |
31 |
Correct |
599 ms |
613964 KB |
Output is correct |
32 |
Correct |
549 ms |
613880 KB |
Output is correct |
33 |
Correct |
505 ms |
613612 KB |
Output is correct |
34 |
Correct |
512 ms |
613636 KB |
Output is correct |
35 |
Correct |
504 ms |
613496 KB |
Output is correct |
36 |
Correct |
505 ms |
613520 KB |
Output is correct |
37 |
Correct |
502 ms |
613624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
506 ms |
613648 KB |
Output is correct |
2 |
Correct |
512 ms |
613548 KB |
Output is correct |
3 |
Correct |
520 ms |
613576 KB |
Output is correct |
4 |
Correct |
512 ms |
613596 KB |
Output is correct |
5 |
Correct |
507 ms |
613624 KB |
Output is correct |
6 |
Correct |
502 ms |
613476 KB |
Output is correct |
7 |
Correct |
505 ms |
613584 KB |
Output is correct |
8 |
Correct |
504 ms |
613504 KB |
Output is correct |
9 |
Correct |
505 ms |
613476 KB |
Output is correct |
10 |
Correct |
502 ms |
613612 KB |
Output is correct |
11 |
Correct |
523 ms |
613480 KB |
Output is correct |
12 |
Correct |
520 ms |
613680 KB |
Output is correct |
13 |
Correct |
500 ms |
613512 KB |
Output is correct |
14 |
Correct |
530 ms |
613532 KB |
Output is correct |
15 |
Correct |
507 ms |
613576 KB |
Output is correct |
16 |
Correct |
508 ms |
613624 KB |
Output is correct |
17 |
Correct |
552 ms |
613772 KB |
Output is correct |
18 |
Correct |
541 ms |
613624 KB |
Output is correct |
19 |
Correct |
602 ms |
613560 KB |
Output is correct |
20 |
Correct |
505 ms |
613652 KB |
Output is correct |
21 |
Correct |
513 ms |
613512 KB |
Output is correct |
22 |
Correct |
514 ms |
613696 KB |
Output is correct |
23 |
Correct |
508 ms |
613596 KB |
Output is correct |
24 |
Correct |
513 ms |
613604 KB |
Output is correct |
25 |
Correct |
1892 ms |
613872 KB |
Output is correct |
26 |
Correct |
1861 ms |
613880 KB |
Output is correct |
27 |
Correct |
1868 ms |
613880 KB |
Output is correct |
28 |
Correct |
530 ms |
613928 KB |
Output is correct |
29 |
Correct |
532 ms |
613868 KB |
Output is correct |
30 |
Correct |
544 ms |
613824 KB |
Output is correct |
31 |
Correct |
599 ms |
613964 KB |
Output is correct |
32 |
Correct |
549 ms |
613880 KB |
Output is correct |
33 |
Correct |
1452 ms |
617440 KB |
Output is correct |
34 |
Correct |
2145 ms |
617592 KB |
Output is correct |
35 |
Correct |
3599 ms |
617472 KB |
Output is correct |
36 |
Correct |
1498 ms |
617552 KB |
Output is correct |
37 |
Execution timed out |
5073 ms |
617336 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5083 ms |
613528 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
506 ms |
613496 KB |
Output is correct |
2 |
Execution timed out |
5043 ms |
636164 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
506 ms |
613648 KB |
Output is correct |
2 |
Correct |
512 ms |
613548 KB |
Output is correct |
3 |
Correct |
520 ms |
613576 KB |
Output is correct |
4 |
Correct |
512 ms |
613596 KB |
Output is correct |
5 |
Correct |
507 ms |
613624 KB |
Output is correct |
6 |
Correct |
502 ms |
613476 KB |
Output is correct |
7 |
Correct |
505 ms |
613584 KB |
Output is correct |
8 |
Correct |
504 ms |
613504 KB |
Output is correct |
9 |
Correct |
505 ms |
613476 KB |
Output is correct |
10 |
Correct |
502 ms |
613612 KB |
Output is correct |
11 |
Correct |
523 ms |
613480 KB |
Output is correct |
12 |
Correct |
520 ms |
613680 KB |
Output is correct |
13 |
Correct |
500 ms |
613512 KB |
Output is correct |
14 |
Correct |
530 ms |
613532 KB |
Output is correct |
15 |
Correct |
507 ms |
613576 KB |
Output is correct |
16 |
Correct |
508 ms |
613624 KB |
Output is correct |
17 |
Correct |
552 ms |
613772 KB |
Output is correct |
18 |
Correct |
541 ms |
613624 KB |
Output is correct |
19 |
Correct |
602 ms |
613560 KB |
Output is correct |
20 |
Correct |
505 ms |
613652 KB |
Output is correct |
21 |
Correct |
513 ms |
613512 KB |
Output is correct |
22 |
Correct |
514 ms |
613696 KB |
Output is correct |
23 |
Correct |
508 ms |
613596 KB |
Output is correct |
24 |
Correct |
513 ms |
613604 KB |
Output is correct |
25 |
Correct |
1892 ms |
613872 KB |
Output is correct |
26 |
Correct |
1861 ms |
613880 KB |
Output is correct |
27 |
Correct |
1868 ms |
613880 KB |
Output is correct |
28 |
Correct |
530 ms |
613928 KB |
Output is correct |
29 |
Correct |
532 ms |
613868 KB |
Output is correct |
30 |
Correct |
544 ms |
613824 KB |
Output is correct |
31 |
Correct |
599 ms |
613964 KB |
Output is correct |
32 |
Correct |
549 ms |
613880 KB |
Output is correct |
33 |
Correct |
1452 ms |
617440 KB |
Output is correct |
34 |
Correct |
2145 ms |
617592 KB |
Output is correct |
35 |
Correct |
3599 ms |
617472 KB |
Output is correct |
36 |
Correct |
1498 ms |
617552 KB |
Output is correct |
37 |
Execution timed out |
5073 ms |
617336 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |