# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
143756 |
2019-08-15T03:08:51 Z |
ondrah |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
636068 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) ? 32 - __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) ? 32 - __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++) {
for(int r2 = r1; r2 <= n-2; r2++) {
int maxC2 = m-2;
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 >= min(a[r1-1][cc], 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:62:11: warning: unused variable 'colGood' [-Wunused-variable]
bool colGood = true;
^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
504 ms |
613500 KB |
Output is correct |
2 |
Incorrect |
505 ms |
613496 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
504 ms |
613500 KB |
Output is correct |
2 |
Incorrect |
505 ms |
613496 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
504 ms |
613500 KB |
Output is correct |
2 |
Incorrect |
505 ms |
613496 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
504 ms |
613500 KB |
Output is correct |
2 |
Incorrect |
505 ms |
613496 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
506 ms |
613636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
505 ms |
613516 KB |
Output is correct |
2 |
Execution timed out |
5144 ms |
636068 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
504 ms |
613500 KB |
Output is correct |
2 |
Incorrect |
505 ms |
613496 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |