Submission #1237168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237168		MuhammadSaram	Rectangles (IOI19_rect)	C++20	59 / 100	4488 ms	1114112 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

long long count_rectangles(vector<vector<int>> a)
{
	int n=a.size(), m=a[0].size();
	vector<short> iv[n][n];
	for (int i=0;i<n;i++)
	{
		for (int j=0,mx=0;j<m;mx=0,j++)
			for (int k=i+1;k+1<n;k++)
			{
				mx=max(mx,a[k][j]);
				if (mx>=min(a[i][j],a[k+1][j]))
					iv[i+1][k].push_back(j);
			}
		for (int k=i+1;k<n;k++)
			iv[i+1][k].push_back(m), iv[i+1][k].shrink_to_fit();
	}
	bool val[n][m][m]={};
	for (int i=0;i<n;i++)
		for (int j=0,mx=0;j<m;j++,mx=0)
			for (int k=j+1;k+1<m;k++)
			{
				mx=max(mx,a[i][k]);
				if (mx<min(a[i][j],a[i][k+1])) val[i][j][k+1]=1;
			}
	long long ans=0;
	for (int i=1;i<n-1;i++)
		for (int j=0;j<m;j++)
			for (int k=j+2;k<m;k++)
			{
				for (int l=i;l+1<n;l++)
				{
					if (!val[l][j][k]) break;
					int x=upper_bound(iv[i][l].begin(), iv[i][l].end(), j)-begin(iv[i][l]);
					if (iv[i][l][x]>=k)
						ans++;
				}
			}
	
	return ans;
}

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