Why can't find the subsequence?

Question

Algorithms

Good evening. The task is to check if an array is a subsequence of another on the segment [l; r]. All my solutions (one normal, linear, another a little faster) break down, scoring 40 points, and the verdict is unknown to me (it seems to me that aphids).

Here's what's faster, based on indexes

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();
  }
}

Can this solution be TLE-configured at all, is it linear? What could be wrong?

Answer 1

You have a solution in O(MN), when as much as possible in O(M log N).
You say it's linear, but you're doing a linear number of operations on each element of array b. It's slow. Your problem is that you store all indexes for each value simply in a list and then naively search there for the first occurrence greater than the given limit. You can store the list in a Set. So I don’t know if he knows how to search for the first element greater than the given limit, like a C ++ set. If not, then you can stupidly store sorted lists of indexes, then you can do a bean search there.