Submission #1066529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066529		HD1	Rectangles (IOI19_rect)	C++14	15 / 100	566 ms	83224 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define sz(s) int (s.size())
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAX=1e6;
ll n,m;
ll mxf[82][82][82], mxc[82][82][82];
vector< vector<int> > A;
void loco(vector<int> s, int x){//filas
	for(int i=1; i<m-1; i++){
		int mx=s[i];
		for(int j=i; j<m-1; j++){
			mx=max(mx,s[j]);
			mxf[x][i][j]=mx;
		}
	}
	return;
}
void loca(vector<int> s, int x){//columnas
	for(int i=1; i<n-1; i++){
		int mx=s[i];
		for(int j=i; j<n-1; j++){
			mx=max(mx,s[j]);
			mxc[x][i][j]=mx;
		}
	}
	return;
}
bool validf(int mx, int i, int l, int r){
	return A[i][l-1]>mx && A[i][r+1]>mx;
}
bool validc(int mx, int j, int l, int r){
	return A[l-1][j]>mx && A[r+1][j]>mx;
}
bool rectangle(int a, int b, int x, int y){
	bool good=true;
	for(int i=a; i<=x; i++){//por filas
		good&=validf(mxf[i][b][y], i, b, y);
	}
	for(int j=b; j<=y; j++){//por columnas
		good&=validc(mxc[j][a][x], j, a, x);
	}
	return good;
}
int fijo(int i1, int j1){
	int ans=0;
	for(int i=i1; i<n-1; i++){
		for(int j=j1; j<m-1; j++){
			if(rectangle(i1, j1, i, j)) ans++;
		}
	}
	return ans;
}
long long count_rectangles(vector< vector<int> > a) {
	A=a;
	n=sz(a);
	m=sz(a[0]);
	for(int i=0; i<n; i++){
		loco(a[i], i);
	}
	vector<int> c;
	for(int j=0; j<m; j++){
		for(int i=0; i<n; i++){
			c.pb(a[i][j]);
		}
		loca(c,j);
		c.clear();
	}
	int ans=0;
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			ans+=fijo(i,j);
		}
	}
	return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/

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