Submission #432387

#	Time	Username	Problem	Language	Result	Execution time	Memory
432387		Berted	Rectangles (IOI19_rect)	C++14	100 / 100	4992 ms	633904 KiB

rect

#include "rect.h"
#include <stack>
#include <vector>
#include <algorithm>
#include <iostream>
#define pii pair<int, int>
#define ppi pair<pii, int>
#define ppp pair<pii, pii>
#define fst first
#define snd second
#define ll long long
#define vi vector<int>
#define vpi vector<pii>
using namespace std;

const int MX = 2505;

int N, M;

struct BIT
{
	int A[MX] = {};
	inline void upd(int x, int v)
	{
		for (; x <= N; x += x & (-x)) A[x] += v;
	}
	inline int qry(int x)
	{
		int ret = 0;
		for (; x; x -= x & (-x)) ret += A[x];
		return ret;
	}
	inline int query(int L, int R) {return qry(R + 1) - qry(L);}
	inline void update(int x, int v) {upd(x + 1, v);}
};

vector<int> Hor[MX * MX];
vector<pii> Ver[MX * MX];
vector<pii> Col[MX];
vector<pii> Ins[MX];

BIT DS[MX];
ll ans = 0;

inline int getIndex(int N, int L, int R)
{
	return N * (N + 1) / 2 - (N - L) * (N - L + 1) / 2 + (R - L);
}

ll count_rectangles(vector<vector<int>> a) 
{
	N = a.size(); M = a.front().size();

	if (N < 3 || M < 3) return 0;

	for (int i = 1; i + 1 < N; i++)
	{
		vector<int> S;
		for (int j = 0; j < M; j++)
		{
			while (S.size() && a[i][S.back()] < a[i][j]) 
			{
				if (S.back() + 1 < j) 
				{
					//cerr << "ROW " << i << ": " << S.back() + 1 << ", " << j - 1 << "\n";
					Hor[getIndex(M, S.back() + 1, j - 1)].push_back(i);
				}
				S.pop_back();
			}
			if (S.size() && S.back() + 1 < j) 
			{
				//cerr << "ROW " << i << ": " << S.back() + 1 << ", " << j - 1 << "\n";
				Hor[getIndex(M, S.back() + 1, j - 1)].push_back(i);
			}
			while (S.size() && a[i][S.back()] == a[i][j]) S.pop_back();
			S.push_back(j);
		}
	}

	for (int j = 1; j + 1 < M; j++)
	{
		vector<int> S;
		for (int i = 0; i < N; i++)
		{
			while (S.size() && a[S.back()][j] < a[i][j]) 
			{
				if (S.back() + 1 < i) 
				{
					Col[j].push_back({S.back() + 1, i - 1});
					//cerr << "COLUMN " << j << ": " << S.back() + 1 << ", " << i - 1 << "\n";
					if (Ver[getIndex(N, S.back() + 1, i - 1)].size() && Ver[getIndex(N, S.back() + 1, i - 1)].back().snd == j - 1) Ver[getIndex(N, S.back() + 1, i - 1)].back().snd++;
					else Ver[getIndex(N, S.back() + 1, i - 1)].push_back({j, j});
				}
				S.pop_back();
			}
			if (S.size() && S.back() + 1 < i) 
			{
				Col[j].push_back({S.back() + 1, i - 1});
				//cerr << "COLUMN " << j << ": " << S.back() + 1 << ", " << i - 1 << "\n";
				if (Ver[getIndex(N, S.back() + 1, i - 1)].size() && Ver[getIndex(N, S.back() + 1, i - 1)].back().snd == j - 1) Ver[getIndex(N, S.back() + 1, i - 1)].back().snd++;
				else Ver[getIndex(N, S.back() + 1, i - 1)].push_back({j, j});
			}
			while (S.size() && a[S.back()][j] == a[i][j]) S.pop_back();
			S.push_back(i);
		}
	}

	for (int i = 1; i + 1 < M; i++)
	{
		for (const auto &x : Col[i])
		{
			auto it = prev(upper_bound(Ver[getIndex(N, x.fst, x.snd)].begin(), Ver[getIndex(N, x.fst, x.snd)].end(), make_pair(i + 1, -1)));
			//cerr << i << ": " << it -> snd << " - " << x.fst << ", " << x.snd << "\n";
			Ins[it -> snd].push_back(x);
		}

		for (int j = M - 2; j >= i; j--)
		{
			for (const auto &x : Ins[j]) {DS[x.snd].update(x.fst, 1);}

			int L = -MX, pv = -MX;
			for (const auto &x : Hor[getIndex(M, i, j)])
			{
				if (pv + 1 < x) {L = x;}
				ans += DS[x].query(L, x);
				pv = x;
			}

			Ins[j].clear();
		}

		for (const auto &x : Col[i]) {DS[x.snd].update(x.fst, -1);}
	}

	return ans;
}

• 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