Skip to Content
CTRL K

Made Up

Editorial oficial (C++) 

Explicación

Como NN puede llegar hasta 10510^5, tardaría demasiado iterar por todos los valores posibles de (i,j)(i, j).

En su lugar, recorremos todos los valores posibles de jj y determinamos cuántos valores de ii pueden emparejarse con él. Para ello, necesitamos determinar cuántos elementos de AA son iguales a BCjB_{C_j} para todo j∈[1,N]j \in [1, N]. Esto se puede hacer con un mapa y un poco de precomputación.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#include <iostream>
#include <map>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int n;
	std::cin >> n;
 
	vector<int> a(n);
	vector<int> b(n);
	vector<int> c(n);
	for (int &i : a) { std::cin >> i; }
	for (int &i : b) { std::cin >> i; }
	for (int &i : c) { std::cin >> i; }
 
	// Guarda, para cada número de A, cuántas veces aparece en total
	std::map<int, int> a_occ_num;
	for (int i : a) { a_occ_num[i]++; }
 
	/*
	 * Para cada valor posible de C_j,
	 * vemos cuántos valores de i son compatibles con él.
	 */
	long long valid_pairs = 0;
	for (int cj : c) { valid_pairs += a_occ_num[b[cj - 1]]; }
	cout << valid_pairs << endl;
}
import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		read.readLine();  // n no se necesita
		int[] a = Arrays.stream(read.readLine().split(" "))
		              .mapToInt(Integer::parseInt)
		              .toArray();
		int[] b = Arrays.stream(read.readLine().split(" "))
		              .mapToInt(Integer::parseInt)
		              .toArray();
		int[] c = Arrays.stream(read.readLine().split(" "))
		              .mapToInt(Integer::parseInt)
		              .toArray();
 
		// Guarda, para cada número de A, cuántas veces aparece en total
		Map<Integer, Integer> aOccNum = new HashMap<>();
		for (int i : a) { aOccNum.put(i, aOccNum.getOrDefault(i, 0) + 1); }
 
		/*
		 * Para cada valor posible de C_j,
		 * vemos cuántos valores de i son compatibles con él.
		 */
		long validPairs = 0;
		for (int cj : c) { validPairs += aOccNum.getOrDefault(b[cj - 1], 0); }
		System.out.println(validPairs);
	}
}
input()  # n no se necesita
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
 
# Guarda, para cada número de A, cuántas veces aparece en total
occ_a_num = {}
for i in a:
	if i not in occ_a_num:
		occ_a_num[i] = 0
	occ_a_num[i] += 1
 
valid_pairs = 0
"""
Para cada valor posible de C_j,
vemos cuántos valores de i son compatibles con él.
"""
for cj in c:
	valid_pairs += occ_a_num.get(b[cj - 1], 0)
 
print(valid_pairs)
Fundamentos