Submission #792258

#	Time	Username	Problem	Language	Result	Execution time	Memory
792258		APROHACK	Rectangles (IOI19_rect)	C++17	37 / 100	5014 ms	39628 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std;
vector<vector<int>>matrix, nxtBigR, nxtBigUp, temp;

struct cuad{
	int ddH, htH, midH, midW, ddW, htW;
	int value;
	pair<int, int>pos;
	cuad *LU, *LD, *RU, *RD; // si es linea horizontal, solo LD, RD, 
	// linea Vertical, LU, LD.
	bool hor, ver;
	cuad(int lH, int rH, int lW, int rW){
		ddH = lH;
		htH = rH;
		ddW = lW;
		htW = rW;
		midH = (ddH + htH)/2;
		midW = (ddW + htW)/2;
		hor = ddH == htH;
		ver = ddW == htW;
		if(ddH != htH or ddW != htW){
			if(hor and ! ver){
				LD = new cuad(ddH, htH, ddW,  midW);
				RD = new cuad(ddH, htH, midW+1, htW);
				if(LD->value > RD->value){
					value = LD->value;
					pos = LD->pos;
				}else{
					value = RD->value;
					pos = RD->pos;
				}
			}else if(ver and !hor){
				LD = new cuad(ddH, midH, ddW, htW);
				LU = new cuad(midH + 1, htH, ddW, htW);
				if(LD->value > LU->value){
					value = LD->value;
					pos = LD->pos;
				}else{
					value = LU->value;
					pos = LU->pos;
				}
			}else{
				LD = new cuad(ddH, midH, ddW, midW);
				RU = new cuad(midH+1, htH, midW+1, htW);
				
				LU = new cuad(midH+1, htH, ddW, midW);
				RD = new cuad(ddH, midH, midW +1, htW);
				value = max(LD->value, RD->value);
				value = max(value, max(RU->value, LU->value));
				if(LD->value == value){
					pos = LD->pos;
				}else if(RU->value == value){
					pos = RU->pos;
				}else if(LU->value == value){
					pos = LU->pos;
				}else{
					pos = RD->pos;
				}
			}
		}else{
			value = temp[ddH][ddW];
			pos = {ddH, ddW};
		}
	}
	pair<int, pair<int, int > > query(int lH, int rH, int lW, int rW){
		if(lH == ddH and rH == htH and lW == ddW and rW == htW)return {value, pos};
		if(rH <= midH and rW <= midW){
			return LD->query(lH, rH, lW, rW);
		}
		if(lH > midH and lW > midH){
			return RU ->query(lH, rH, lW, rW);
		}
		if(rH<=midH and lW > midH){
			return RD ->query(lH, rH, lW, rW);
		}
		if(lH > midH and rW <= midW){
			return LU ->query(lH, rH, lW, rW);
		}
		
		if(rH <= midH){
			return max(LD ->query(lH, rH, lW, midW), RD ->query(lH, rH, midW+1, rW));
		}else if( lH > midH){
			return max(LU ->query(lH, rH, lW, midW), RU ->query(lH, rH, midW+1, rW));
		}
		
		if(rW <= midW){
			return max(LD ->query(lH, midH, lW, rW), LU ->query(midH+1, rH, lW, rW));
		}else if( lW > midW){
			return max(RD ->query(lH, midH, lW, rW), RU ->query(midH+1, rH, lW, rW));
		}
		
		return max(max(LD->query(lH, midH, lW, midW), RD->query(lH, midH, midW+1, rW)), max(LU->query(midH+1, htH, lW, midH), RU->query(midH+1, rH, midW+1, rW)));
	}
};

cuad *grandeR, *grandeU, *matris, *grandeL, *grandeD;
int N, M;



long long count_rectangles(std::vector<std::vector<int> > a) {
	N = a.size();
	M = a[0].size();
	matrix = a;
	ll ans = 0;
	for(int i = 1 ; i < N-1 ; i ++){
		for(int j = 1 ; j < M-1 ; j ++){
			for(int ii = i ; ii < N-1 ; ii++){
				for(int jj = j ; jj < M-1 ; jj++){
					bool valid = true;
					for(int x = i ; x <= ii ; x ++){
						for(int pp = j ; pp <= jj ; pp ++){
							int val = matrix[x][pp];
							if(!(val < matrix[x][j-1] and val < matrix[x][jj+1] and val < matrix[i-1][pp] and val < matrix[ii +1][pp])){
								pp = jj +1;
								x = ii + 1;
								valid = false;
							}
						}
					}
					if(valid)ans ++;
				}
			}
		}
	}
	
	return ans;
}

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