Submission #1082205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082205		aykhn	Rectangles (IOI19_rect)	C++17	100 / 100	3206 ms	812552 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

struct BIT
{
	int n;
	vector<int> ft;
	void init(int N)
	{
		n = N + 5;
		ft.assign(n + 5, 0);
	}
	void add(int pos, int val)
	{
		for (pos = pos + 1; pos <= n; pos += pos & -pos) ft[pos] += val;
	}
	int get(int pos, int res = 0)
	{
		for (pos = pos + 1; pos > 0; pos -= pos & -pos) res += ft[pos];
		return res;
	}
};

const int MXN = 25e2 + 5;

int mpR[MXN][MXN], mpC[MXN][MXN], nwR[MXN][MXN], nwC[MXN][MXN];

long long count_rectangles(vector<vector<int32_t>> a) 
{
	int n = a.size(), m = a[0].size();
	int pre[n][m], nxt[n][m];
	vector<int> addR[n][m], addC[n][m];
	vector<int> v;
	for (int i = 0; i < n; i++)
	{
		v.clear();
		for (int j = 0; j < m; j++)
		{
			while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back();
			if (!v.empty()) pre[i][j] = v.back() + 1;
			else pre[i][j] = -1;
			v.push_back(j);
		}
		v.clear();
		for (int j = m - 1; j >= 0; j--)
		{
			while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back();
			if (!v.empty()) nxt[i][j] = v.back() - 1;
			else nxt[i][j] = -1;
			v.push_back(j);
		}
		for (int j = 0; j < m; j++)
		{
			if (nxt[i][j] == -1 || pre[i][j] == -1) continue;
			addR[i][nxt[i][j]].push_back(pre[i][j]);
		}
	}
	for (int j = 0; j < m; j++)
	{
		v.clear();
		for (int i = 0; i < n; i++)
		{
			while (!v.empty() && a[v.back()][j] <= a[i][j]) v.pop_back();
			if (!v.empty()) pre[i][j] = v.back() + 1;
			else pre[i][j] = -1;
			v.push_back(i);
		}
		v.clear();
		for (int i = n - 1; i >= 0; i--)
		{
			while (!v.empty() && a[v.back()][j] <= a[i][j]) v.pop_back();
			if (!v.empty()) nxt[i][j] = v.back() - 1;
			else nxt[i][j] = -1;
			v.push_back(i);
		}
		for (int i = 0; i < n; i++)
		{
			if (nxt[i][j] == -1 || pre[i][j] == -1) continue;
			addC[nxt[i][j]][j].push_back(pre[i][j]);
		}
	}
	BIT ft;
	ft.init(max(n, m));
	long long res = 0;
	vector<array<int, 2>> v1, v2;
	vector<array<int, 2>> vR, vC, vnwR, vnwC;
	vector<int> f(max(n, m), 0);
	for (int j = 0; j < m; j++)
	{
		for (array<int, 2> &x : vnwC) nwC[x[0]][x[1]] = 0;
		vnwC.clear();
		for (int i = 0; i < n; i++)
		{
			for (array<int, 2> &x : vnwR) nwR[x[0]][x[1]] = 0;
			vnwR.clear();
			v1.clear(), v2.clear();
			vector<int> nw;
			for (int &k : addR[i][j])
			{
				if (f[k]) continue;
				nw.push_back(k);
				f[k] = 1;
			}
			for (int &k : nw) f[k] = 0;
			swap(addR[i][j], nw);
			nw.clear();
			for (int &k : addC[i][j])
			{
				if (f[k]) continue;
				nw.push_back(k);
				f[k] = 1;
			}
			for (int &k : nw) f[k] = 0;
			swap(addC[i][j], nw);
			for (int &x : addR[i][j])
			{
				int x1 = j - x + 1, y1 = mpR[x][j] + 1;
				v1.push_back({x1, y1});
			}
			for (int &y : addC[i][j])
			{
				int x2 = i - y + 1, y2 = mpC[y][i] + 1;
				v2.push_back({x2, y2});
			}
			sort(v1.begin(), v1.end(), [&](const array<int, 2> &x, const array<int, 2> &y)
			{
				return x[1] < y[1];
			});
			sort(v2.begin(), v2.end(), [&](const array<int, 2> &x, const array<int, 2> &y)
			{
				return x[0] < y[0];
			});
			int y = 0;
			for (int x = 0; x < v1.size(); x++)
			{
				while (y < v2.size() && v1[x][1] >= v2[y][0])
				{
					ft.add(v2[y][1], 1);
					y++;
				}
				res = res + 1LL * ft.get(max(n, m)) - ft.get(v1[x][0] - 1);
			}
			for (int x = 0; x < y; x++) ft.add(v2[x][1], -1);
			for (int &x : addR[i][j]) 
			{
				nwR[x][j] = mpR[x][j] + 1;
				vnwR.push_back({x, j});
			}
			for (int &y : addC[i][j]) 
			{
				nwC[y][i] = mpC[y][i] + 1;
				vnwC.push_back({y, i});
			}
			for (array<int, 2> &x : vR) mpR[x[0]][x[1]] = 0;
			for (array<int, 2> &x : vnwR) mpR[x[0]][x[1]] = nwR[x[0]][x[1]];
			vR = vnwR;
		}
		for (array<int, 2> &x : vC) mpC[x[0]][x[1]] = 0;
		for (array<int, 2> &x : vnwC) mpC[x[0]][x[1]] = nwC[x[0]][x[1]];
		vC = vnwC;
	}
	return res;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:136:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |    for (int x = 0; x < v1.size(); x++)
      |                    ~~^~~~~~~~~~~
rect.cpp:138:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     while (y < v2.size() && v1[x][1] >= v2[y][0])
      |            ~~^~~~~~~~~~~

• 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