Submission #143731

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
143731	2019-08-15T01:43:03 Z	ondrah	Rectangles (IOI19_rect)	C++14	Compilation error	0 ms	0 KB

rect

#include "rect.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;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:23:2: error: 'memset' was not declared in this scope
  memset(rowMax,-1,sizeof(rowMax));
  ^~~~~~
rect.cpp:23:2: note: suggested alternative: 'fd_set'
  memset(rowMax,-1,sizeof(rowMax));
  ^~~~~~
  fd_set