Почему не получается найти подпоследовательность?

Question

[BitNeBolt]

Добрый вечер. В задаче требуется проверить, является ли массив подпоследовательностью другого на отрезке [l; r]. Все мои решения (одно обычное, линейное, другое чуть быстрее) ломаются, набрав 40 баллов, а вердикт мне неизвестен (мне кажется, что тля).

Вот то, что побыстрее, основано на индексах

import java.util.*;
import java.io.*;

public class D {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		var inds = new HashMap<Integer, List<Integer>>();

		int n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			int x = sc.nextInt();
			var adjs = inds.getOrDefault(x, new ArrayList<Integer>());
			adjs.add(i);
			inds.put(x, adjs);
		}

		int q = sc.nextInt();
		for (; q > 0; q--) {
			int l = sc.nextInt()-1; 
			int r = sc.nextInt()-1;
			int m = sc.nextInt();

			boolean ok = true;

			var b = new int[m];
			for (int i = 0; i < m; i++) {
				b[i] = sc.nextInt();
			}

			int prev = -1;
			for (int i = 0; i < m; i++) {
				int next = -1;
				int x = b[i];

				if (!inds.keySet().contains(x)) {
					ok = false;
					break;
				}

				var adjs = inds.get(x);
				for (int j = 0; j < adjs.size(); j++) {
					int ind = adjs.get(j);
					if (ind > prev && ind >= l && ind <= r) {
						next = ind;
						break;
					}
				}

				if (next == -1) {
					ok = false;
					break;
				} else {
					prev = next;
				}
			}

			out.println(ok ? "YES" : "NO");
		}

		out.close();
		sc.close();
	}
}

Может ли это решение вообще TLE-шиться, оно же линейно? В чем может быть ошибка?

Comments

[BitNeBolt]

Если что, это виртуальное участие на кф.

Answer 1

[Wataru]

У вас решение за O(MN), когда как можно за O(M log N).

Вы говорите, что оно линейно, но вы выполняете линейное количество операций на каждый элемент массива b. Это медленно. Ваша проблема в том, что вы храните все индексы для каждого значения просто в списке и потом там наивно ищите первое вхождение больше данной границы. Можно список хранить в Set. Вот я не в курсе, умеет ли он, как C++-шный set искать первый элемент больше заданной границы. Если нет, то можно тупо хранить отсортированые списки индексов, тогда там можно будет делать бинпоиск.

Comments

[BitNeBolt]

Спасибо

[Alexandroppolus]

У вас решение за O(MN), когда как можно за O(M log N).

Это на одну проверку, или на всё про всё? Одну проверку можно и за O(N), что в данных условиях может оказаться быстрее, если r-l не намного больше чем m.

[Wataru]

Alexandroppolus, O(MN) за все. Не понял вторую часть комментария.

[BitNeBolt]

Alexandroppolus, худший случай, когда решение MN - это когда в а содержится N одинаковых чисел, b = a, l=1, r=N. Оно будет просматривать все N индексов N раз.

Поэтому MN

[Alexandroppolus]

Wataru, там ещё есть Q - сколько запросов. Я имел в виду, что O(N) - это один запрос, а всё вместе будет O(QN).

Получить O(N) на одну проверку легко: в массиве b ставим указатель pos на первый элемент, обходим массив а от l до r, если a[i] == b[pos], то делаем pos++, потом смотрим что b пройден до конца.

[BitNeBolt]

Alexandroppolus, такое решение, кстати, тоже не проходит.

[Wataru]

Alexandroppolus, Так там и Q и M и N - сотни тысяч в задаче. Один запрос или одно число из запроса (потому что ограничение на сумму размеров всех запросов есть в конце условия) надо делать быстрее чем за линию.