Solução Informática Intermediário - Semana 53 - Problema 1

Por Samyra Almeida

Para resolver esse problema é necessário conhecimento sobre a técnica de sweep line e a estrutura da BIT (ou Binary Indexed Tree).

Segundo o enunciado temos que, dados dois pontos $A$ e $B$ e sendo $A_x < B_x$ , temos que $B$ não domina $A$ se $A_y > B_y$ .

Agora vamos utilizar a ideia do sweep line, primeiro iremos ordenar todos os pontos pela coordenada $X$ . Com isso, note que dado qualquer conjunto válido $C = {A, B, ..., N}$ , sabemos que $A_x < B_x < ... < N_x$ e $A_y > B_y > ... > N_y$ . Calculando a quantidade de conjuntos válidos até um determinado ponto $i$ temos que $quantidade[i] =$ $\sum_{j = 1}^{i - 1} quantidade[j],$ $\forall$ $j_y > i_y$ .

Para calcularmos a quantidade de conjuntos válidos para o ponto $i$ de forma eficiente iremos utilizar uma estrutura de dados chamada BIT (ou Binary Indexed Tree) na coordenada $Y$ em que cada índice $y$ da BIT guarda a quantidade de conjuntos válidos no qual $y$ faz parte. De inicio a BIT estará vazia, mas iremos adicionando os conjuntos conforme o nosso algoritmo estiver rodando. Para descobrirmos quantos conjuntos válidos $i$ participa basta consultarmos a soma de $i_y + 1$ até $m$ , onde $m$ é igual a maior coordenada $Y$ dentre todos os pontos presentes em $S$ , fazendo $quantidade[i] = sum(i_y + 1) + 1$ . Após isso, iremos atualizar a $BIT[i]$ fazendo $add(i_y,$ $quantidade[i])$ . Enfim ao rodarmos esse algoritmo para todos os $N$ pontos temos que a resposta final será igual ao $\sum_{k = 1}^{N} quantidade[k]$ .

Segue o código para maior entendimento:

	#include <bits/stdc++.h>

	using namespace std;

	const int maxn = 1e5+10, mod = 1e9+7;

	int n, m, bit[maxn], quantidade[maxn];

	struct point{
	int x, y;
	bool operator<(const point& o) const{
	if(x != o.x) return x < o.x;
	return y < o.y;
	}
	} p[maxn];

	void add(int i, int v){

	while(i)
	{
	bit[i] = (bit[i]%mod + v)%mod;
	i-=(i&-i);
	}
	}

	int sum(int i)
	{
	int soma = 0;

	for(; i <= m ; i += (i&-i))
	{
	soma = (soma%mod +bit[i])%mod;
	}
	return soma;
	}

	int main()
	{
	cin >> n;

	for(int i = 1 ; i <= n ; ++i)
	{
	cin >> p[i].x >> p[i].y;
	m = max(m, p[i].y);
	}

	sort(p + 1, p + n + 1);

	int resp = 0;

	for(int i = 1 ; i <= n ; ++i)
	{
	quantidade[i] = (sum(p[i].y + 1)%mod + 1)%mod;
	add(p[i].y, quantidade[i]);
	resp = (resp%mod + quantidade[i])%mod;
	}

	cout << resp << "\n";

	return 0;
	}

view raw

ps-intermediario-s53-p1.cpp

hosted with ❤ by GitHub