Submission #817658

#	Time	Username	Problem	Language	Result	Execution time	Memory
817658		prvocislo	Rectangles (IOI19_rect)	C++17	100 / 100	4030 ms	607904 KiB

rect

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

const int maxn = 2505;
vector<int> e[maxn][maxn];
int ri[maxn], li[maxn];
ll ans = 0;
struct obdl
{
	int x1, y1, x2, y2, t;
};
void make(const vector<vector<int> > &a, vector<obdl> &o, int t)
{
	int n = a.size(), m = a[0].size();
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++) ri[j] = m, li[j] = -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) e[j + 1][ri[j] - 1].push_back(i);
			if (li[j] != -1 && ri[li[j]] >= j) e[li[j] + 1][j - 1].push_back(i);
		}
	}
	for (int y1 = 0; y1 < m; y1++) for (int y2 = y1; y2 < m; y2++)
	{
		for (int i = 0; i < e[y1][y2].size(); i++) if (!i || e[y1][y2][i - 1] + 1 < e[y1][y2][i])
		{
			int j = i;
			while (j + 1 < e[y1][y2].size() && e[y1][y2][j] >= e[y1][y2][j + 1] - 1) j++;
			o.push_back({ e[y1][y2][i], y1, e[y1][y2][j], y2, t });
		}
		e[y1][y2].clear();
	}
}
int st[maxn];
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;
}
bool cmp(obdl a, obdl b)
{
	if (a.x2 == b.x2) return a.t > b.t;
	return a.x2 < b.x2;
}
ll count_rectangles(vector<vector<int> > a)
{
	int n = a.size(), m = a[0].size();
	vector<obdl> ob;
	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];
	make(b, ob, 2);
	for (obdl& i : ob) swap(i.x1, i.y1), swap(i.x2, i.y2);
	make(a, ob, 1);
	sort(ob.begin(), ob.end(), cmp);
	for (int i = 0; i < ob.size(); i++)
	{
		if (ob[i].t == 1) for (int x1 = ob[i].x1; x1 <= ob[i].x2; x1++) e[x1][ob[i].y1].push_back(i);
		if (ob[i].t == 2) for (int y1 = ob[i].y1; y1 <= ob[i].y2; y1++) e[ob[i].x1][y1].push_back(i);
	}
	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 (int u : e[x][y])
		{
			if (ob[u].t == 2) upd(ob[u].y2, 1), all++;
			else sum += all - query(ob[u].y2 - 1);
		}
		for (int u : e[x][y]) if (ob[u].t == 2) upd(ob[u].y2, -1);
		ans += sum;
		//cout << sum << " \n"[y == m - 2];
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'void make(const std::vector<std::vector<int> >&, std::vector<obdl>&, int)':
rect.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int i = 0; i < e[y1][y2].size(); i++) if (!i || e[y1][y2][i - 1] + 1 < e[y1][y2][i])
      |                   ~~^~~~~~~~~~~~~~~~~~
rect.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    while (j + 1 < e[y1][y2].size() && e[y1][y2][j] >= e[y1][y2][j + 1] - 1) j++;
      |           ~~~~~~^~~~~~~~~~~~~~~~~~
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<obdl>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for (int i = 0; i < ob.size(); i++)
      |                  ~~^~~~~~~~~~~

• 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: 28 / 28