Submission #824917

#	Time	Username	Problem	Language	Result	Execution time	Memory
824917		caganyanmaz	Rectangles (IOI19_rect)	C++17	50 / 100	312 ms	111072 KiB

rect

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



constexpr static int UP = 0;
constexpr static int DOWN = 1;
constexpr static int LEFT = 2;
constexpr static int RIGHT = 3;
constexpr static int MXN = 2505;

struct Fenwick
{
	int v[MXN];
	int get(int i) { int res = 0; for (++i; i > 0; i-=i&(-i)) res += v[i]; return res; }
	void set(int i, int val) { for (++i; i < MXN; i+=i&(-i)) v[i] += val; }
	int get(int l, int r) { return get(r) - get(l); }
	void reset() { fill(v, v + MXN, 0); } 
};

int vals[MXN][MXN][4];
void calculate_cell(int i, int j, const vector<vector<int32_t>>& a)
{
	int ii, jj;
	for (ii = max<int>(i-1, 0); ii > 0; ii--)
		if (a[ii][j] >= a[i][j])
			break;
	vals[i][j][UP] = ii;
	for (ii = min<int>(i+1, a.size()-1); ii < a.size() - 1; ii++)
		if (a[ii][j] >= a[i][j])
			break;
	vals[i][j][DOWN] = ii;
	for (jj = max<int>(j-1, 0); jj > 0; jj--)
		if (a[i][jj] >= a[i][j])
			break;
	vals[i][j][LEFT] = jj;
	for (jj = min<int>(j+1, a[0].size()-1); jj < a[0].size() - 1; jj++)
		if (a[i][jj] >= a[i][j])
			break;
	vals[i][j][RIGHT] = jj;
}

int first[MXN];
int last[MXN];
int nxt[MXN];
Fenwick fw;


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 special_subtask(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;
			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;
}
long long count_rectangles(vector<vector<int32_t>> a)
{
	if (a.size() > 200)
		return special_subtask(a);
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < a[0].size(); j++)
		{
			calculate_cell(i, j, a);
		}
	}
	int res = 0;
	for (int u = 0; u < a.size()-1; u++)
	{
		fill(first, first + MXN, 0);
		fill(last, last + MXN, MXN);
		for (int d = u+2; d < a.size(); d++)
		{
			fw.reset();
			for (int i = 0; i < a[0].size(); i++)
				first[i] = max<int>(first[i], vals[d-1][i][LEFT]); // Getting the leftmost possible for each of them 
			for (int i = 0; i < a[0].size(); i++)
				last[i] = min<int>(last[i], vals[d-1][i][RIGHT]);
			vector<vector<int>> rrr(a[0].size());
			for (int i = 0; i < a[0].size(); i++)
				rrr[first[i]].pb(i);
			vector<int> pending;
			for (int i = 0; i < a[0].size(); i++)
			{
				pending.pb(i);
				if (vals[u][i][DOWN] < d || vals[d][i][UP] > u)
				{
					for (int j : pending)
						nxt[j] = i;
					pending.clear();
				}
			}
			for (int j : pending)
				nxt[j] = a[0].size();
			for (int i = 0; i < a[0].size(); i++)
			{

				for (int j : rrr[i])
				{
					fw.set(j, 1);
				}
				if (min(last[i], nxt[i+1]) > i+1)
				{
					res += fw.get(i+1, min(last[i], nxt[i+1]));
				}

			}
			
				
		}
	}
	return res;
}

Compilation message (stderr)

rect.cpp: In function 'void calculate_cell(int64_t, int64_t, const std::vector<std::vector<int> >&)':
rect.cpp:32:42: 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]
   32 |  for (ii = min<int>(i+1, a.size()-1); ii < a.size() - 1; ii++)
      |                                       ~~~^~~~~~~~~~~~~~
rect.cpp:40:45: 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]
   40 |  for (jj = min<int>(j+1, a[0].size()-1); jj < a[0].size() - 1; jj++)
      |                                          ~~~^~~~~~~~~~~~~~~~~
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:57: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]
   57 |  if (i < a.size() && i >=0 && j < a[0].size() && j >= 0 && !visited[i][j] && a[i][j] == 0)
      |      ~~^~~~~~~~~~
rect.cpp:57: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]
   57 |  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 special_subtask(std::vector<std::vector<int> >&)':
rect.cpp:68: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]
   68 |  for (int i = 1; i <= a.size(); i++)
      |                  ~~^~~~~~~~~~~
rect.cpp:69: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]
   69 |   for (int j = 1; j <= a[0].size(); j++)
      |                   ~~^~~~~~~~~~~~~~
rect.cpp:72: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]
   72 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~
rect.cpp:74: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]
   74 |   for (int j = 0; j < a[0].size(); j++)
      |                   ~~^~~~~~~~~~~~~
rect.cpp:97: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]
   97 |    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:97: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]
   97 |    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: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:107: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]
  107 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~
rect.cpp:109: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]
  109 |   for (int j = 0; j < a[0].size(); j++)
      |                   ~~^~~~~~~~~~~~~
rect.cpp:115: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]
  115 |  for (int u = 0; u < a.size()-1; u++)
      |                  ~~^~~~~~~~~~~~
rect.cpp:119:23: 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]
  119 |   for (int d = u+2; d < a.size(); d++)
      |                     ~~^~~~~~~~~~
rect.cpp:122:22: 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]
  122 |    for (int i = 0; i < a[0].size(); i++)
      |                    ~~^~~~~~~~~~~~~
rect.cpp:124:22: 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]
  124 |    for (int i = 0; i < a[0].size(); i++)
      |                    ~~^~~~~~~~~~~~~
rect.cpp:127:22: 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]
  127 |    for (int i = 0; i < a[0].size(); i++)
      |                    ~~^~~~~~~~~~~~~
rect.cpp:130:22: 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]
  130 |    for (int i = 0; i < a[0].size(); i++)
      |                    ~~^~~~~~~~~~~~~
rect.cpp:142:22: 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]
  142 |    for (int i = 0; i < a[0].size(); i++)
      |                    ~~^~~~~~~~~~~~~

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