oj.uz

Submission #143732

# Submission time Handle Problem Language Result Execution time Memory
143732 2019-08-15T01:43:24 Z ondrah Rectangles (IOI19_rect) C++14
0 / 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[2555][2555][12]; //

int getRowMax(int r, int c1, int c2) {
	int d = 0;
	while((1<<(d+1)) <= (c2-c1))
		d++;
	return max(rowMax[d][r][c1], rowMax[d][r][max(c1, c2-(1<<d))]);
}
int getColMax(int c, int r1, int r2) {
	int d = 0;
	while((1<<(d+1)) <= (r2-r1))
		d++;
	return max(rowMax[d][r1][c], rowMax[d][max(r1, r2-(1<<d))][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-1, 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-1, 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 613660 KB Output is correct
2 Incorrect 508 ms 613620 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 613660 KB Output is correct
2 Incorrect 508 ms 613620 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 613660 KB Output is correct
2 Incorrect 508 ms 613620 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 613660 KB Output is correct
2 Incorrect 508 ms 613620 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5131 ms 613572 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 613464 KB Output is correct
2 Execution timed out 5134 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 501 ms 613660 KB Output is correct
2 Incorrect 508 ms 613620 KB Output isn't correct
3 Halted 0 ms 0 KB -