Submission #817536

#	Time	Username	Problem	Language	Result	Execution time	Memory
817536		prvocislo	Rectangles (IOI19_rect)	C++17	72 / 100	3362 ms	1048576 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll ans = 0;
struct obdl
{
	int x1, y1, x2, y2, t;
};
vector<obdl> make(vector<vector<int> > a)
{
	int n = a.size(), m = a[0].size();
	vector<vector<vector<int> > > end(m, vector<vector<int> > (m));
	for (int i = 0; i < n; i++)
	{
		vector<int> ri(m, m), li(m, -1);
		vector<int> st;
		for (int j = 0; j < m; j++) // najdeme najblizsi vacsi
		{
			while (!st.empty() && a[i][j] > a[i][st.back()]) st.pop_back();
			if (!st.empty() && st.back() + 1 < j) li[j] = st.back();
			st.push_back(j);
		}
		st.clear();
		for (int j = m - 1; j >= 0; j--) // najdeme najblizsi vacsi
		{
			while (!st.empty() && a[i][j] > a[i][st.back()]) st.pop_back();
			if (!st.empty() && st.back() - 1 > j) ri[j] = st.back();
			st.push_back(j);
		}
		for (int j = 0; j < m; j++)
		{
			if (ri[j] != m && li[ri[j]] <= j) end[j + 1][ri[j] - 1].push_back(i);
			if (li[j] != -1 && ri[li[j]] >= j) end[li[j] + 1][j - 1].push_back(i);
		}
	}
	vector<obdl>o;
	for (int y1 = 0; y1 < m; y1++) for (int y2 = y1; y2 < m; y2++) for (int i = 0; i < end[y1][y2].size(); i++) if (!i || end[y1][y2][i - 1] + 1 < end[y1][y2][i])
	{
		int j = i;
		while (j + 1 < end[y1][y2].size() && end[y1][y2][j] >= end[y1][y2][j + 1] - 1) j++;
		o.push_back({ end[y1][y2][i], y1, end[y1][y2][j], y2 });
	}
	return o;
}
const int maxn = 2505;
int st[maxn * 2];
void upd(int i, int x)
{
	for (; i < maxn; i = (i | (i + 1))) st[i] += x;
}
int query(int r)
{
	int ans = 0;
	for (; r >= 0; r = (r & (r + 1)) - 1) ans += st[r];
	return ans;
}
struct udaj { int x, y, t; };
ll count_rectangles(vector<vector<int> > a)
{
	int n = a.size(), m = a[0].size();
	vector<vector<vector<udaj> > > v(n, vector<vector<udaj> >(m));
	vector<vector<vector<obdl> > > o(n, vector<vector<obdl> >(m));
	vector<obdl> o1 = make(a);
	vector<vector<int> > b(m, vector<int>(n));
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) b[j][i] = a[i][j];
	vector<obdl> o2 = make(b);
	for (obdl& i : o2) i.t = 2, swap(i.x1, i.y1), swap(i.x2, i.y2), o[i.x2][i.y2].push_back(i);
	for (obdl i : o1) i.t = 1, o[i.x2][i.y2].push_back(i);
	for (int x = 0; x < n; x++) for (int y = m - 1; y >= 0; y--) for (obdl i : o[x][y])
	{
		if (i.t == 1) for (int x1 = i.x1; x1 <= i.x2; x1++) v[x1][i.y1].push_back({ x, y, 1 });
		if (i.t == 2) for (int y1 = i.y1; y1 <= i.y2; y1++) v[i.x1][y1].push_back({ x, y, 2 });
	}
	ll ans = 0;
	for (int x = 1; x + 1 < n; x++) for (int y = 1; y + 1 < m; y++)
	{
		ll sum = 0, all = 0;
		for (udaj u : v[x][y])
		{
			if (u.t == 2) upd(u.y, 1), all++;
			else sum += all - query(u.y - 1);
		}
		for (udaj u : v[x][y]) if (u.t == 2) upd(u.y, -1);
		ans += sum;
		//cout << sum << " \n"[y == m - 2];
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'std::vector<obdl> make(std::vector<std::vector<int> >)':
rect.cpp:39:83: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int y1 = 0; y1 < m; y1++) for (int y2 = y1; y2 < m; y2++) for (int i = 0; i < end[y1][y2].size(); i++) if (!i || end[y1][y2][i - 1] + 1 < end[y1][y2][i])
      |                                                                                 ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   while (j + 1 < end[y1][y2].size() && end[y1][y2][j] >= end[y1][y2][j + 1] - 1) j++;
      |          ~~~~~~^~~~~~~~~~~~~~~~~~~~

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