Submission #1210532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210532		bangan	Rectangles (IOI19_rect)	C++20	10 / 100	238 ms	167712 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 2500 + 4;

int l[N][8][N];
int r[N][8][N];
int u[N][8][N];
int d[N][8][N];

int get_l(int k, int i, int j, int ii, int jj) {return l[k][ii+1][jj+1] - l[k][ii+1][j] - l[k][i][jj+1] + l[k][i][j];}
int get_r(int k, int i, int j, int ii, int jj) {return r[k][ii+1][jj+1] - r[k][ii+1][j] - r[k][i][jj+1] + r[k][i][j];}
int get_u(int k, int i, int j, int ii, int jj) {return u[k][ii+1][jj+1] - u[k][ii+1][j] - u[k][i][jj+1] + u[k][i][j];}
int get_d(int k, int i, int j, int ii, int jj) {return d[k][ii+1][jj+1] - d[k][ii+1][j] - d[k][i][jj+1] + d[k][i][j];}

long long count_rectangles(std::vector<std::vector<int>> a) {
	int n = a.size();
	int m = a[0].size();
	for (int i=0; i<n; i++) for (int j=0; j<m; j++) {
		for (int k=j-1; k>=0; k--) if (a[i][j]<a[i][k]) l[k+1][i+1][j+1]=1;
		for (int k=j+1; k<m ; k++) if (a[i][j]<a[i][k]) r[k-1][i+1][j+1]=1;
		for (int k=i-1; k>=0; k--) if (a[i][j]<a[k][j]) u[k+1][i+1][j+1]=1;
		for (int k=i+1; k<n ; k++) if (a[i][j]<a[k][j]) d[k-1][i+1][j+1]=1;
	}
	// cout << r[1][1][1] << ' ' << r[1][1][2] << '\n';
	// cout << r[1][2][1] << ' ' << r[1][2][2] << '\n';
	for (int k=0; k<m; k++) for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) {
		l[k][i][j] += l[k][i-1][j] + l[k][i][j-1] - l[k][i-1][j-1];
		r[k][i][j] += r[k][i-1][j] + r[k][i][j-1] - r[k][i-1][j-1];
	}
	for (int k=0; k<n; k++) for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) {
		u[k][i][j] += u[k][i-1][j] + u[k][i][j-1] - u[k][i-1][j-1];
		d[k][i][j] += d[k][i-1][j] + d[k][i][j-1] - d[k][i-1][j-1];
	}
	// cout << r[1][1][1] << ' ' << r[1][1][2] << '\n';
	// cout << r[1][2][1] << ' ' << r[1][2][2] << '\n';
	int ans=0;
	for (int i=1; i+1<n; i++) for (int j=1; j+1<m; j++) {
		for (int ii=i; ii+1<n; ii++) for (int jj=j; jj+1<m; jj++) {
			int s = (ii-i+1) * (jj-j+1);
			// if (i==j && j==ii && ii==jj && i==1) cout << (get_l(j,i,j,ii,jj)==s) << (get_r(jj,i,j,ii,jj)==s) << (get_u(i,i,j,ii,jj)==s) << (get_d(ii,i,j,ii,jj)==s) << '\n';
			ans += get_l(j,i,j,ii,jj)==s && get_r(jj,i,j,ii,jj)==s && get_u(i,i,j,ii,jj)==s && get_d(ii,i,j,ii,jj)==s;
		}
	}
	return ans;
}

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