Submission #143740

#	Time	Username	Problem	Language	Result	Execution time	Memory
143740		ondrah	Rectangles (IOI19_rect)	C++14	0 / 100	5122 ms	636192 KiB

rect

#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+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++;
	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: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28