Submission #432381

#	Time	Username	Problem	Language	Result	Execution time	Memory
432381		Berted	Rectangles (IOI19_rect)	C++14	Compilation error	0 ms	0 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); V.push_back({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;

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[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[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[S.back() + 1][i - 1].size() && Ver[S.back() + 1][i - 1].back().snd == j - 1) Ver[S.back() + 1][i - 1].back().snd++;
					else Ver[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[S.back() + 1][i - 1].size() && Ver[S.back() + 1][i - 1].back().snd == j - 1) Ver[S.back() + 1][i - 1].back().snd++;
				else Ver[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[x.fst][x.snd].begin(), Ver[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[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;
}

Compilation message (stderr)

rect.cpp: In member function 'void BIT::update(int, int)':
rect.cpp:34:51: error: 'V' was not declared in this scope
   34 |  inline void update(int x, int v) {upd(x + 1, v); V.push_back({x + 1, -v});}
      |                                                   ^