oj.uz

Submission #143751

# Submission time Handle Problem Language Result Execution time Memory
143751 2019-08-15T02:50:23 Z ondrah Rectangles (IOI19_rect) C++14
15 / 100
 5000 ms 636024 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]; //

int getRowMax(int r, int c1, int c2) {
	int d = 0;
	while((1<<(d+1)) <= (c2-c1+1))
		d++;
	return max(rowMax[d][r][c1], rowMax[d][r][max(c1, c2-(1<<d)+1)]);
}
int getColMax(int c, int r1, int r2) {
	int d = 0;
	while((1<<(d+1)) <= (r2-r1+1))
		d++;
	// [d][r1][c] je od r1 do r1+2^d-1 vcetne
	return max(colMax[d][r1][c], colMax[d][max(r1, 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++) {
				for(int c2 = c1; c2 <= m-2; c2++) {
					bool good = true;
					for(int rr = r1; rr <= r2; rr++) {
						if(getRowMax(rr, c1, c2) >= min(a[rr][c1-1], a[rr][c2+1])) {
							//printf("r1=%d, r2=%d, c1=%d, c2=%d, ERR AT rr=%d\n", r1, r2, c1, c2, rr);
							good = false;
							break;
						}
					}
					bool colGood = true;
					for(int cc = c1; cc <= c2; cc++) {
						if(getColMax(cc, r1, r2) >= min(a[r1-1][cc], a[r2+1][cc])) {
						//	printf("r1=%d, r2=%d, c1=%d, c2=%d, ERR AT cc=%d [up: %d, down: %d, max: %d]\n", r1, r2, c1, c2, cc, a[r1-1][cc], a[r2+1][cc], getColMax(cc, r1, r2));
							good = colGood = false;
							break;
						}
					}
					if(good) {
						ans++;
						//printf("r1=%d, r2=%d, c1=%d, c2=%d\n", r1, r2, c1, c2);
					}
				}
			}
		}
	}

	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 613496 KB Output is correct
2 Correct 549 ms 613668 KB Output is correct
3 Correct 515 ms 613500 KB Output is correct
4 Correct 543 ms 613752 KB Output is correct
5 Correct 511 ms 613556 KB Output is correct
6 Correct 514 ms 613496 KB Output is correct
7 Correct 511 ms 613540 KB Output is correct
8 Correct 515 ms 613496 KB Output is correct
9 Correct 538 ms 613700 KB Output is correct
10 Correct 526 ms 613556 KB Output is correct
11 Correct 532 ms 613524 KB Output is correct
12 Correct 537 ms 613564 KB Output is correct
13 Correct 512 ms 613624 KB Output is correct
14 Correct 510 ms 613648 KB Output is correct
15 Correct 508 ms 613668 KB Output is correct
16 Correct 508 ms 613456 KB Output is correct
17 Correct 511 ms 613496 KB Output is correct
18 Correct 508 ms 613496 KB Output is correct
19 Correct 509 ms 613624 KB Output is correct
20 Correct 524 ms 613500 KB Output is correct
21 Correct 511 ms 613468 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 613496 KB Output is correct
2 Correct 549 ms 613668 KB Output is correct
3 Correct 515 ms 613500 KB Output is correct
4 Correct 543 ms 613752 KB Output is correct
5 Correct 511 ms 613556 KB Output is correct
6 Correct 514 ms 613496 KB Output is correct
7 Correct 511 ms 613540 KB Output is correct
8 Correct 515 ms 613496 KB Output is correct
9 Correct 538 ms 613700 KB Output is correct
10 Correct 526 ms 613556 KB Output is correct
11 Correct 532 ms 613524 KB Output is correct
12 Correct 537 ms 613564 KB Output is correct
13 Correct 512 ms 613624 KB Output is correct
14 Correct 510 ms 613648 KB Output is correct
15 Correct 508 ms 613668 KB Output is correct
16 Correct 508 ms 613456 KB Output is correct
17 Correct 863 ms 613632 KB Output is correct
18 Correct 833 ms 613660 KB Output is correct
19 Correct 843 ms 613624 KB Output is correct
20 Correct 717 ms 613752 KB Output is correct
21 Correct 726 ms 613680 KB Output is correct
22 Correct 711 ms 613596 KB Output is correct
23 Correct 724 ms 613640 KB Output is correct
24 Correct 563 ms 613624 KB Output is correct
25 Correct 511 ms 613496 KB Output is correct
26 Correct 508 ms 613496 KB Output is correct
27 Correct 509 ms 613624 KB Output is correct
28 Correct 524 ms 613500 KB Output is correct
29 Correct 511 ms 613468 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 613496 KB Output is correct
2 Correct 549 ms 613668 KB Output is correct
3 Correct 515 ms 613500 KB Output is correct
4 Correct 543 ms 613752 KB Output is correct
5 Correct 511 ms 613556 KB Output is correct
6 Correct 514 ms 613496 KB Output is correct
7 Correct 511 ms 613540 KB Output is correct
8 Correct 515 ms 613496 KB Output is correct
9 Correct 538 ms 613700 KB Output is correct
10 Correct 526 ms 613556 KB Output is correct
11 Correct 532 ms 613524 KB Output is correct
12 Correct 537 ms 613564 KB Output is correct
13 Correct 512 ms 613624 KB Output is correct
14 Correct 510 ms 613648 KB Output is correct
15 Correct 508 ms 613668 KB Output is correct
16 Correct 508 ms 613456 KB Output is correct
17 Correct 863 ms 613632 KB Output is correct
18 Correct 833 ms 613660 KB Output is correct
19 Correct 843 ms 613624 KB Output is correct
20 Correct 717 ms 613752 KB Output is correct
21 Correct 726 ms 613680 KB Output is correct
22 Correct 711 ms 613596 KB Output is correct
23 Correct 724 ms 613640 KB Output is correct
24 Correct 563 ms 613624 KB Output is correct
25 Execution timed out 5115 ms 613880 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 613496 KB Output is correct
2 Correct 549 ms 613668 KB Output is correct
3 Correct 515 ms 613500 KB Output is correct
4 Correct 543 ms 613752 KB Output is correct
5 Correct 511 ms 613556 KB Output is correct
6 Correct 514 ms 613496 KB Output is correct
7 Correct 511 ms 613540 KB Output is correct
8 Correct 515 ms 613496 KB Output is correct
9 Correct 538 ms 613700 KB Output is correct
10 Correct 526 ms 613556 KB Output is correct
11 Correct 532 ms 613524 KB Output is correct
12 Correct 537 ms 613564 KB Output is correct
13 Correct 512 ms 613624 KB Output is correct
14 Correct 510 ms 613648 KB Output is correct
15 Correct 508 ms 613668 KB Output is correct
16 Correct 508 ms 613456 KB Output is correct
17 Correct 863 ms 613632 KB Output is correct
18 Correct 833 ms 613660 KB Output is correct
19 Correct 843 ms 613624 KB Output is correct
20 Correct 717 ms 613752 KB Output is correct
21 Correct 726 ms 613680 KB Output is correct
22 Correct 711 ms 613596 KB Output is correct
23 Correct 724 ms 613640 KB Output is correct
24 Correct 563 ms 613624 KB Output is correct
25 Execution timed out 5115 ms 613880 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5134 ms 613584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 613448 KB Output is correct
2 Execution timed out 5128 ms 636024 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 613496 KB Output is correct
2 Correct 549 ms 613668 KB Output is correct
3 Correct 515 ms 613500 KB Output is correct
4 Correct 543 ms 613752 KB Output is correct
5 Correct 511 ms 613556 KB Output is correct
6 Correct 514 ms 613496 KB Output is correct
7 Correct 511 ms 613540 KB Output is correct
8 Correct 515 ms 613496 KB Output is correct
9 Correct 538 ms 613700 KB Output is correct
10 Correct 526 ms 613556 KB Output is correct
11 Correct 532 ms 613524 KB Output is correct
12 Correct 537 ms 613564 KB Output is correct
13 Correct 512 ms 613624 KB Output is correct
14 Correct 510 ms 613648 KB Output is correct
15 Correct 508 ms 613668 KB Output is correct
16 Correct 508 ms 613456 KB Output is correct
17 Correct 863 ms 613632 KB Output is correct
18 Correct 833 ms 613660 KB Output is correct
19 Correct 843 ms 613624 KB Output is correct
20 Correct 717 ms 613752 KB Output is correct
21 Correct 726 ms 613680 KB Output is correct
22 Correct 711 ms 613596 KB Output is correct
23 Correct 724 ms 613640 KB Output is correct
24 Correct 563 ms 613624 KB Output is correct
25 Execution timed out 5115 ms 613880 KB Time limit exceeded
26 Halted 0 ms 0 KB -