Submission #424038

#	Time	Username	Problem	Language	Result	Execution time	Memory
424038		schse	Rectangles (IOI19_rect)	C++17	15 / 100	5072 ms	521676 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

struct staticrmq
{
	vector<vector<int>> arr;
	void init(const vector<int> &a)
	{
		arr.resize(a.size(), vector<int>(__lg(a.size()) + 1));
		for (int i = 0; i < a.size(); i++)
			arr[i][0] = a[i];
		for (int e = 1; e < arr[0].size(); e++)
			for (int i = 0; i < a.size() - (1 << e) + 1; i++)
				arr[i][e] = max(arr[i][e - 1], arr[i + (1 << (e - 1))][e - 1]);
	}
	int query(int l, int r)
	{
		int lv = __lg(abs(r - l));
		return max(arr[l][lv], arr[r - (1 << lv) + 1][lv]);
	}
};

vector<staticrmq> rows, cols;

bool check(int r1, int r2, int c1, int c2, std::vector<std::vector<int>> &a)
{

	for (int e = c1 + 1; e < c2; e++)
	{
		int q = rows[e].query(r1 + 1, r2 - 1);
		if (q >= a[r1][e] || q >= a[r2][e])
			return false;
	}

	for (int i = r1 + 1; i < r2; i++)
	{
		int q = cols[i].query(c1 + 1, c2 - 1);
		if (q >= a[i][c1] || q >= a[i][c2])
			return false;
	}
	return true;
}
/*
bool check(int r1, int r2, int c1, int c2, std::vector<std::vector<int>> &a)
{
	for (int e = c1 + 1; e < c2; e++)
	{
		for (int i = r1 + 1; i < r2; i++)
		{
			if (a[i][e] >= a[r1][e] || a[i][e] >= a[r2][e])
				return false;
			if (a[i][e] >= a[i][c1] || a[i][e] >= a[i][c2])
				return false;
		}
	}
	return true;
}
*/
long long count_rectangles(std::vector<std::vector<int>> a)
{

	rows.resize(a[0].size());
	cols.resize(a.size());
	for (int i = 0; i < a.size(); i++)
		cols[i].init(a[i]);
	for (int i = 0; i < a[0].size(); i++)
	{
		vector<int> v;
		for (int e = 0; e < a.size(); e++)
			v.push_back(a[e][i]);
		rows[i].init(v);
	}

	long long count = 0;

	for (int r1 = 0; r1 < a.size(); r1++)
	{
		for (int c1 = 0; c1 < a[0].size(); c1++)
		{
			for (int r2 = r1 + 2; r2 < a.size(); r2++)
			{
				for (int c2 = c1 + 2; c2 < a[0].size(); c2++)
				{
					if (check(r1, r2, c1, c2, a))
						count++;
				}
			}
		}
	}

	return count;
}

Compilation message (stderr)

rect.cpp: In member function 'void staticrmq::init(const std::vector<int>&)':
rect.cpp:14:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for (int i = 0; i < a.size(); i++)
      |                   ~~^~~~~~~~~~
rect.cpp:16:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for (int e = 1; e < arr[0].size(); e++)
      |                   ~~^~~~~~~~~~~~~~~
rect.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |    for (int i = 0; i < a.size() - (1 << e) + 1; i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~
rect.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for (int i = 0; i < a[0].size(); i++)
      |                  ~~^~~~~~~~~~~~~
rect.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int e = 0; e < a.size(); e++)
      |                   ~~^~~~~~~~~~
rect.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int r1 = 0; r1 < a.size(); r1++)
      |                   ~~~^~~~~~~~~~
rect.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (int c1 = 0; c1 < a[0].size(); c1++)
      |                    ~~~^~~~~~~~~~~~~
rect.cpp:84:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    for (int r2 = r1 + 2; r2 < a.size(); r2++)
      |                          ~~~^~~~~~~~~~
rect.cpp:86:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int c2 = c1 + 2; c2 < a[0].size(); c2++)
      |                           ~~~^~~~~~~~~~~~~

• 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