Submission #143758

#	Time	Username	Problem	Language	Result	Execution time	Memory
143758		ondrah	Rectangles (IOI19_rect)	C++14	27 / 100	5083 ms	636164 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[12][2555][2555]; //

inline int getRowMax(int r, int c1, int c2) {
	int d = (c2-c1) ? 31 - __builtin_clz(c2-c1) : 0;
	return max(rowMax[d][r][c1], rowMax[d][r][c2-(1<<d)+1]);
}
inline int getColMax(int c, int r1, int r2) {
	int d = (r2-r1) ? 31 - __builtin_clz(r2-r1) : 0;
	return max(colMax[d][r1][c], colMax[d][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++) {
			int maxC2G = m-2;
			for(int r2 = r1; r2 <= n-2; r2++) {
				int maxC2 = min(m-2, maxC2G);
				for(int c2 = c1; c2 <= maxC2; c2++) {
					bool good = true;
					bool breakc2 = false;
					for(int rr = r1; rr <= r2; rr++) {
						int rm = getRowMax(rr, c1, c2);
						if(rm >= a[rr][c1-1]) {
							//printf("r1=%d, r2=%d, c1=%d, c2=%d, ERR AT rr=%d\n", r1, r2, c1, c2, rr);
							good = false;
							breakc2 = true;
							break;
						}
						if(rm >= a[rr][c2+1]) {
							good = false;
							break;
						}
					}
					if(breakc2) break;
					bool colGood = true;
					for(int cc = c1; cc <= c2; cc++) {
						int rm = getColMax(cc, r1, r2);
						if(rm >= a[r1-1][cc]) {
							good = false;
							maxC2 = maxC2G = cc-1;
							breakc2 = true;
							break;
						}
						else if(rm >= a[r2+1][cc]) {
							good = false;
							maxC2 = cc-1;
							breakc2 = true;
							break;
						}
					}
					if(breakc2) break;
					if(good) {
						ans++;
						//printf("r1=%d, r2=%d, c1=%d, c2=%d\n", r1, r2, c1, c2);
					}
				}
			}
		}
	}

	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:63:11: warning: unused variable 'colGood' [-Wunused-variable]
      bool colGood = true;
           ^~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28