Submission #723311

#	Time	Username	Problem	Language	Result	Execution time	Memory
723311		LittleCube	Rectangles (IOI19_rect)	C++14	27 / 100	5091 ms	28748 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

/*
enumerate l, r, i and iterate j => O(n^5)
enumerate l, iterate r, and enumerate i, j => O(n^4)
condition:
pov 1: manage all possible end points in i-axis, we already know the other j-axis what's the furthest point to query,
so
  l     r
4 8 7 5 6
---------
7 4 1 3 5 i
	  --
9 7 2 4 2
	--  -
9 1 7 3 6
----
5 7 5 2 7
4 5 1 5 6

what is the possible endpoint?

there is only one possible endpoint? no.
so we know that for each position, we can calculate what's the possible endpoint in O(nnm)
enumerate l, r, we can precalc for each i last possible inner part and compare.
*/

struct BIT
{
	int bit[705], N;
	void init(int n)
	{
		N = n;
		for (int i = 1; i <= N; i++)
			bit[i] = 0;
	}
	void modify(int pos, int val)
	{
		for (int i = pos + 1; i <= N; i += (i & -i))
			bit[i] += val;
	}
	int query(int pos)
	{
		int ans = 0;
		for (int i = pos + 1; i; i -= (i & -i))
			ans += bit[i];
		return ans;
	}

} bit[705];

int N, M, p[705][705], last[705], down[705][705], in[705][705], able[705];
ll ans;

ll count_rectangles(vector<vector<int>> a)
{
	N = a.size(), M = a[0].size();
	// a[i + 1..j][l + 1..r]
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			down[i][j] = N;
			for (int k = i + 1; k < N; k++)
				if (a[k][j] >= a[i][j])
				{
					down[i][j] = k - 1;
					break;
				}
		}
	for (int l = 0; l + 1 < M; l++)
	{
		// cerr << "check l " << l << '\n';
		for (int i = 0; i < N; i++)
		{
			int mx = 0;
			for (int r = l + 1; r + 1 < M; r++)
			{
				mx = max(mx, a[i][r]);
				p[i][r] = (a[i][l] > mx && mx < a[i][r + 1]);
			}
		}
		vector<pii> mono[705];

		for (int r = l + 1; r + 1 < M; r++)
			last[r] = N;
		for (int i = N - 2; i >= 0; i--)
		{
			// cerr << " check i " << i << '\n';
			for (int r = l + 1; r + 1 < M; r++)
			{
				if (!p[i + 1][r])
					last[r] = i;
				while (!mono[r].empty() && mono[r].back().F <= a[i + 1][r])
					mono[r].pop_back();
				mono[r].emplace_back(pii(a[i + 1][r], i + 1));
			}
			for (int j = i + 1; j < N; j++)
				able[j] = 1;
			for (int r = l + 1; r + 1 < M; r++)
			{
				for (auto [val, j] : mono[r])
				{
					// cerr << "  r " << r << " checks j " << j << '\n';
					if (j > i + 1 && j - 1 <= down[i][r])
					{

						//if ((j  - 1 <= last[r] && able[j] > 0))
						//	cerr << l << ' ' << r << "  " << i << ' ' << j << '\n';
						ans += (j - 1 <= last[r] && able[j] > 0);
						able[j]++;
					}
					// cerr << ans << '\n';
				}
				for (int j = i + 1; j < N; j++)
					able[j]--;
			}
		}
	}

	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:108:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |     for (auto [val, j] : mono[r])
      |               ^

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