XXX OI - Zadanie Pociąg towarowy

Question

Witam,
Zadanie: https://szkopul.edu.pl/problemset/problem/U5dJG9pa-TT5cl-5Fkf8SrwB/statement/
Oto mój pomysł: przechodząc wszystkie elementy listy zawierającej wagony zanotowane przez Bajtka, dla każdego sprawdzam następujące warunki: Czy Bitek kiedykolwiek również zanotował taki wagon? Jeśli tak, to czy index wagonu Bajtka jest większy lub równy indexowi znalezionemu w notatkach Bitka (jeśli jest mniejszy, oznaczałoby to, że Bitek dopisał coś dodatkowo), oraz, jeśli ten warunek jest spełniony, to sprawdzam jeszcze, czy wagon o index + 1 znaleziony u Bitka jest gdzieś po prawo od elementu obecnie przeglądanego w liście Bajtka.

Uznałem, że jeśli wszystkie te warunki są spełnione, to wagon może być zanotowany przez Bitka. Jeśli dowolny z warunków spełniony nie jest, to nie może. Zaimplementowałem to z użyciem binary searcha:
 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool val_exists(const vector<pair<int, int>>& bajtek_val_sorted, int val, int min_idx) {
	if (val == -1) {
		return true;
	}

	if (min_idx == bajtek_val_sorted.size())
		return false;

	int l = 0;
	int r = bajtek_val_sorted.size() - 1;

	while (l <= r) {
		int mid = (l + r) / 2;

		if (bajtek_val_sorted[mid].first == val) {
			if (bajtek_val_sorted[mid].second >= min_idx)
				return true;

			l = mid + 1;
		}
		else if (bajtek_val_sorted[mid].first < val) {
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}

	return false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	std::cout.tie(nullptr);

	int n, m, k;
	cin >> n >> m >> k;

	// val, original index
	vector<pair<int, int>> bajtek_val_sorted(n);
	vector<pair<int, int>> bitek_val_sorted(m);

	vector<int> bitek(m);

	for (int i = 0; i < n; ++i) {
		cin >> bajtek_val_sorted[i].first;
		bajtek_val_sorted[i].second = i;
	}

	for (int i = 0; i < m; ++i) {
		cin >> bitek_val_sorted[i].first;
		bitek_val_sorted[i].second = i;

		bitek[i] = bitek_val_sorted[i].first;
	}

	sort(bajtek_val_sorted.begin(), bajtek_val_sorted.end());
	sort(bitek_val_sorted.begin(), bitek_val_sorted.end());

	vector<int> result(n);
	for (const pair<int, int>& b : bajtek_val_sorted) {
		int val = b.first;
		int idx = b.second;

		int l = 0;
		int r = m - 1;
		bool valid = false;
		while (l <= r) {
			int mid = (l + r) / 2;

			if (bitek_val_sorted[mid].first == val) {
				int rngbr_idx = bitek_val_sorted[mid].second + 1;
				if (bitek_val_sorted[mid].second <= idx && val_exists(bajtek_val_sorted, (rngbr_idx < bitek.size() ? bitek[rngbr_idx] : -1), idx + 1)) {
					valid = true;
					break;
				}

				r = mid - 1;
			}
			else if (bitek_val_sorted[mid].first < val) {
				l = mid + 1;
			}
			else {
				r = mid - 1;
			}
		}

		result[idx] = valid;
	}

	for (int i = 0; i < n; ++i)
		std::cout << result[i] << ' ';
}

No i cóż. Zadziałało dla testu 3, gdzie każdy rodzaj wagonu występuje maksymalnie 1 raz (czyli w sumie 15pkt). Zły jest pomysł, czy kod?

EDIT: Ponieważ kiedy każy wagon jest unikatowy, to jeśli sprawdzimy jednego z sąsiadów (lewy lub prawy), w moim przypadku wybrałem prawego, i on się zgadza, to mamy pewność, że znaleźliśmy dobre miejsce. Jeśli wagony nie są unikatowe, powinniśmy sprawdzić nie tylko sąsiadów po obu stronach, ale tak na prawdę przejrzeć całą listę Bitka na prawo i na lewo. Czyli potencjalnie O(N*M*logM). Jak to optymalnie rozwiązać?