oj.uz

Submission #143749

# Submission time Handle Problem Language Result Execution time Memory
143749 2019-08-15T02:32:14 Z ondrah Rectangles (IOI19_rect) C++14
0 / 100
 5000 ms 613624 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 = 1;
	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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 509 ms 613624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 509 ms 613624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 509 ms 613624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 509 ms 613624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 577 ms 613568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 509 ms 613624 KB Output isn't correct
2 Halted 0 ms 0 KB -