oj.uz

Submission #824917

# Submission time Handle Problem Language Result Execution time Memory
824917 2023-08-14T11:54:54 Z caganyanmaz Rectangles (IOI19_rect) C++17
50 / 100
 312 ms 111072 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 428 KB Output is correct
21 Correct 1 ms 340 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 428 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 14 ms 1008 KB Output is correct
23 Correct 14 ms 1028 KB Output is correct
24 Correct 14 ms 1004 KB Output is correct
25 Correct 16 ms 980 KB Output is correct
26 Correct 15 ms 980 KB Output is correct
27 Correct 16 ms 1008 KB Output is correct
28 Correct 16 ms 980 KB Output is correct
29 Correct 6 ms 852 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 14 ms 1008 KB Output is correct
18 Correct 14 ms 1028 KB Output is correct
19 Correct 14 ms 1004 KB Output is correct
20 Correct 16 ms 980 KB Output is correct
21 Correct 15 ms 980 KB Output is correct
22 Correct 16 ms 1008 KB Output is correct
23 Correct 16 ms 980 KB Output is correct
24 Correct 6 ms 852 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 304 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 1 ms 428 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 223 ms 2992 KB Output is correct
31 Correct 202 ms 3012 KB Output is correct
32 Correct 202 ms 3028 KB Output is correct
33 Correct 217 ms 2844 KB Output is correct
34 Correct 220 ms 2900 KB Output is correct
35 Correct 232 ms 3072 KB Output is correct
36 Correct 224 ms 3044 KB Output is correct
37 Correct 212 ms 3068 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 14 ms 1008 KB Output is correct
18 Correct 14 ms 1028 KB Output is correct
19 Correct 14 ms 1004 KB Output is correct
20 Correct 16 ms 980 KB Output is correct
21 Correct 15 ms 980 KB Output is correct
22 Correct 16 ms 1008 KB Output is correct
23 Correct 16 ms 980 KB Output is correct
24 Correct 6 ms 852 KB Output is correct
25 Correct 223 ms 2992 KB Output is correct
26 Correct 202 ms 3012 KB Output is correct
27 Correct 202 ms 3028 KB Output is correct
28 Correct 217 ms 2844 KB Output is correct
29 Correct 220 ms 2900 KB Output is correct
30 Correct 232 ms 3072 KB Output is correct
31 Correct 224 ms 3044 KB Output is correct
32 Correct 212 ms 3068 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 304 KB Output is correct
35 Correct 2 ms 468 KB Output is correct
36 Correct 1 ms 428 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Incorrect 44 ms 13872 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 824 KB Output is correct
2 Correct 3 ms 832 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 736 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 468 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 428 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 140 ms 52876 KB Output is correct
8 Correct 308 ms 110244 KB Output is correct
9 Correct 301 ms 110792 KB Output is correct
10 Correct 300 ms 110884 KB Output is correct
11 Correct 140 ms 55152 KB Output is correct
12 Correct 278 ms 107080 KB Output is correct
13 Correct 312 ms 111072 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 14 ms 1008 KB Output is correct
18 Correct 14 ms 1028 KB Output is correct
19 Correct 14 ms 1004 KB Output is correct
20 Correct 16 ms 980 KB Output is correct
21 Correct 15 ms 980 KB Output is correct
22 Correct 16 ms 1008 KB Output is correct
23 Correct 16 ms 980 KB Output is correct
24 Correct 6 ms 852 KB Output is correct
25 Correct 223 ms 2992 KB Output is correct
26 Correct 202 ms 3012 KB Output is correct
27 Correct 202 ms 3028 KB Output is correct
28 Correct 217 ms 2844 KB Output is correct
29 Correct 220 ms 2900 KB Output is correct
30 Correct 232 ms 3072 KB Output is correct
31 Correct 224 ms 3044 KB Output is correct
32 Correct 212 ms 3068 KB Output is correct
33 Incorrect 44 ms 13872 KB Output isn't correct
34 Halted 0 ms 0 KB -