Submission #824799

#	Time	Username	Problem	Language	Result	Execution time	Memory
824799		caganyanmaz	Rectangles (IOI19_rect)	C++17	37 / 100	5083 ms	117460 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;

long long count_rectangles(vector<vector<int32_t>> 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 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:53: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]
   53 |  for (int i = 0; i < a.size(); i++)
      |                  ~~^~~~~~~~~~
rect.cpp:55: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]
   55 |   for (int j = 0; j < a[0].size(); j++)
      |                   ~~^~~~~~~~~~~~~
rect.cpp:61: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]
   61 |  for (int u = 0; u < a.size()-1; u++)
      |                  ~~^~~~~~~~~~~~
rect.cpp:65: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]
   65 |   for (int d = u+2; d < a.size(); d++)
      |                     ~~^~~~~~~~~~
rect.cpp:68: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]
   68 |    for (int i = 0; i < a[0].size(); i++)
      |                    ~~^~~~~~~~~~~~~
rect.cpp:70: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]
   70 |    for (int i = 0; i < a[0].size(); i++)
      |                    ~~^~~~~~~~~~~~~
rect.cpp:73: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]
   73 |    for (int i = 0; i < a[0].size(); i++)
      |                    ~~^~~~~~~~~~~~~
rect.cpp:76: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]
   76 |    for (int i = 0; i < a[0].size(); i++)
      |                    ~~^~~~~~~~~~~~~
rect.cpp:88: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]
   88 |    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: 0 / 13
• Subtask 7: 0 / 28