Submission #824908

#	Time	Username	Problem	Language	Result	Execution time	Memory
824908		caganyanmaz	Rectangles (IOI19_rect)	C++17	13 / 100	321 ms	107864 KiB

rect

#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
#include "rect.h"
using namespace std;


void __print(int i) { cerr << i; }
void __print(const char* s) { cerr << s; }
void __print(int32_t i) { cerr << i; }
void __print(bool i) { cerr << (i ? "true" : "false"); } 

template<typename T>
void __print(T& t) { cerr << "{"; int f = 0; for (auto& i : t) { cerr << (f++ ? ", ": ""); __print(i); } cerr << "}"; }
void _print() { cerr << "]\n"; }
template<typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifdef DEBUGGING
#define debug(x...) { cerr << "[" << (#x) << "] = ["; _print(x); }
#else
#define debug(x...) 42
#endif

constexpr static int MXN = 2505;

int pf[MXN][MXN];
bitset<MXN> visited[MXN];

void check_try(int i, int j, queue<array<int, 2>>& q, vector<vector<int32_t>>& a)
{
	if (i < a.size() && i >=0 && j < a[0].size() && j >= 0 && !visited[i][j] && a[i][j] == 0)
	{
		visited[i][j] = true;
		q.push({i, j});
	}
		
}


long long count_rectangles(vector<vector<int32_t>> a)
{
	for (int i = 1; i <= a.size(); i++)
		for (int j = 1; j <= a[0].size(); j++)
			pf[i][j] = pf[i][j-1] + pf[i-1][j] - pf[i-1][j-1] + a[i-1][j-1];
	int res = 0;
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < a[0].size(); j++)
		{
			if (visited[i][j] || a[i][j] == 1)
				continue;
			queue<array<int, 2>> q;
			debug("B");
			q.push({i, j});
			int up = MXN;
			int down = -1;
			int left = MXN;
			int right = -1;
			while (q.size())
			{
				auto [ii, jj] = q.front();
				q.pop();
				check_try(ii+1, jj, q, a);
				check_try(ii, jj+1, q, a);
				check_try(ii, jj-1, q,a );
				check_try(ii-1, jj, q,a );
				up = min(up, ii);
				down = max(down, ii);
				left = min(left, jj);
				right = max(right, jj);
			}
			if (pf[down+1][right+1] - pf[down+1][left] - pf[up][right+1] + pf[up][left] == 0 && down < a.size() - 1&& up > 0 && right < a[0].size() -1 && left > 0)
				res++;
		}
			
	}
	return res;
}

Compilation message (stderr)

rect.cpp: In function 'void check_try(int64_t, int64_t, std::queue<std::array<long int, 2> >&, std::vector<std::vector<int> >&)':
rect.cpp:31:8: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  if (i < a.size() && i >=0 && j < a[0].size() && j >= 0 && !visited[i][j] && a[i][j] == 0)
      |      ~~^~~~~~~~~~
rect.cpp:31:33: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  if (i < a.size() && i >=0 && j < a[0].size() && j >= 0 && !visited[i][j] && a[i][j] == 0)
      |                               ~~^~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int i = 1; i <= a.size(); i++)
      |                  ~~^~~~~~~~~~~
rect.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int j = 1; j <= a[0].size(); j++)
      |                   ~~^~~~~~~~~~~~~~
rect.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~
rect.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int j = 0; j < a[0].size(); j++)
      |                   ~~^~~~~~~~~~~~~
rect.cpp:21:21: warning: statement has no effect [-Wunused-value]
   21 | #define debug(x...) 42
      |                     ^~
rect.cpp:53:4: note: in expansion of macro 'debug'
   53 |    debug("B");
      |    ^~~~~
rect.cpp:72:93: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    if (pf[down+1][right+1] - pf[down+1][left] - pf[up][right+1] + pf[up][left] == 0 && down < a.size() - 1&& up > 0 && right < a[0].size() -1 && left > 0)
      |                                                                                        ~~~~~^~~~~~~~~~~~~~
rect.cpp:72:126: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    if (pf[down+1][right+1] - pf[down+1][left] - pf[up][right+1] + pf[up][left] == 0 && down < a.size() - 1&& up > 0 && right < a[0].size() -1 && left > 0)
      |                                                                                                                        ~~~~~~^~~~~~~~~~~~~~~~

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