Submission #200949

#	Time	Username	Problem	Language	Result	Execution time	Memory
200949		Lawliet	Rectangles (IOI19_rect)	C++17	10 / 100	8 ms	504 KiB

rect

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

using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;

const int MAXN = 2510;
const int INF = 1000000010;

int n, m;

int L[MAXN];
int R[MAXN];
int v[MAXN][MAXN];

void makeHistogram()
{
	int i = 2;

	v[i][0] = v[i][m + 1] = INF;

	for(int j = 1 ; j <= m ; j++)
	{
		int cur = j - 1;

		while( v[i][cur] < v[i][j] ) cur = L[cur];

		L[j] = cur;
	}

	for(int j = m ; j > 0 ; j--)
	{
		int cur = j + 1;

		while( v[i][cur] <= v[i][j] ) cur = R[cur];

		R[j] = cur;
	}
}

long long count_rectangles(vector< vector<int> > a) //Grids pequenos
{
	n = a.size();
	m = a[0].size();

	if( n <= 2 ) return 0;

	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j < m ; j++)
			v[i + 1][j + 1] = a[i][j];

	makeHistogram();

	int ans = 0;

	for(int i = 1 ; i <= m ; i++)
	{
		bool possible = true;

		if( L[i] == 0 || R[i] == m + 1 ) continue;

		for(int j = L[i] + 1 ; j < R[i] ; j++)
			possible = possible && ( v[2][j] < v[1][j] && v[2][j] < v[3][j] );

		if( possible ) ans++;
	}

	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