Submission #1082145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082145		aykhn	Rectangles (IOI19_rect)	C++17	59 / 100	5126 ms	753484 KiB

rect

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

using namespace std;

const int MX = 7e6 + 5;

vector<array<int, 2>> ind[MX];

long long count_rectangles(vector<vector<int>> a) 
{
	int n = a.size(), m = a[0].size();
	set<int> r[n], c[m];
	vector<int> v;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			ind[a[i][j]].push_back({i, j});
		}
	}
	for (int i = 0; i < n; i++) r[i].insert(-1), r[i].insert(m);
	for (int i = 0; i < m; i++) c[i].insert(-1), c[i].insert(n);
	set<array<int, 3>> r1, c1;
	for (int i = MX - 1; i >= 0; i--)
	{
		for (array<int, 2> &x : ind[i])
		{
			int L = *prev(r[x[0]].lower_bound(x[1])), R = *r[x[0]].lower_bound(x[1]);
			if (!(L < 0 || R >= m)) r1.insert({x[0], L + 1, R - 1});
			L = *prev(c[x[1]].lower_bound(x[0])), R = *c[x[1]].lower_bound(x[0]);
			if (!(L < 0 || R >= n)) c1.insert({x[1], L + 1, R - 1});
		}
		for (array<int, 2> &x : ind[i])
		{
			r[x[0]].insert(x[1]);
			c[x[1]].insert(x[0]);
		}
	}
	vector<int> addR[n][m], addC[n][m];
	for (array<int, 3> i : r1) addR[i[0]][i[2]].push_back(i[1]);
	for (array<int, 3> i : c1) addC[i[2]][i[0]].push_back(i[1]);
	int res = 0;
	map<array<int, 2>, int> mpR, mpC;
	for (int j = 0; j < m; j++)
	{
		mpR.clear();
		map<array<int, 2>, int> nwC;
		for (int i = 0; i < n; i++)
		{
			int cnt = 0;
			for (int &x : addR[i][j])
			{
				for (int &y : addC[i][j])
				{
					int x1 = j - x + 1;
					int x2 = i - y + 1;
					int y1 = (mpR.find({x, j}) != mpR.end() ? mpR[{x, j}] : 0) + 1;
					int y2 = (mpC.find({y, i}) != mpC.end() ? mpC[{y, i}] : 0) + 1;
					cnt += (y1 >= x2 && y2 >= x1);
				}
			}
			res += cnt;
			map<array<int, 2>, int> nwR;
			for (int &x : addR[i][j]) nwR[{x, j}] = mpR[{x, j}] + 1;
			for (int &y : addC[i][j]) nwC[{y, i}] = mpC[{y, i}] + 1;
			swap(nwR, mpR);
		}
		swap(nwC, mpC);
	}
	return res;
}

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