Задача с отбора на стажировку про строки "Лучше клавиатуры не сыскать?"

Добрый вечер, уважаемые форумчане!!! Имеется интересная задача с отбора на стажировку. Сразу скажу,что отбор прошел уже месяц как и задача уже неактуальна для других пользователей. Но разобраться хочется, поэтому хотелось бы получить дельный совет касаемо решения этой задачи.

Собственно условие выглядит так:

Начало условия:
Кузя снова не успел сдать реферат по языковым разнообразиям в срок.
«Наверное, у меня какая-то неоптимальная клавиатура.» — подумал Кузя и решил изобрести самую оптимальную клавиатуру для набора одним пальцем. Кузя решил, что его клавиатура будет содержать № рядов с клавишами (разные ряды могут содержать разные количества клавиш). Все клавиши на клавиатуре будут уникальными.
Чтобы оценить качество клавиатуры для набора определенного текста, Кузя ввёл понятие «разнорядности»:

Пусть текст представляет из себя строку S длины К;

Назовём переход между соседними в тексте символами Si-1 и Si(2<= i <= K) разнорядным, если данные символы находятся на различных рядах клавиатуры;

Разнорядность равна количеству разнорядных переходов при наборе техста на заданной
клавиатуре.

Например, пусть текст S равен АВСАD, а клавиатура содержит два ряда клавиш АСи ВD.
В таком случае при наборе текста будет ровно 3 разнорядных перехода:
1. S1 = А в S2= В (ряд 1 в ряд 2);
2. S2 = B в S3= C (ряд 2 в ряд 1);
3. S4 = А в S5= D (ряд 1 в ряд 2);

ФОРМАТ ВВОДА

Первая строка содержит одно целое число N(1 <= N <= 2 * 105) — количество клавиш на
клавиатуре.

Вторая строка содержит N целых чисел сi(0 <= сi <= 109) — идентификаторы символов на клавишах. Гарантируется, что все значения сi различны.

Третья строка содержит N целых чисел ri(1 <= ri <= 109). Число ri задает номер рада на клавиатуре, в котором расположена клавиша с символом сi.

Четвертая строка содержит одно целое число К(1 <= К <= 2 * 105) — количество символов в реферате.

Пятая строка содержит К целых чисел сj(0 <= сj <= 109) — идентификаторы символов
реферата в порядке набора на клавиатуре. Гарантируется, что для любого сj существует такой i,
что sj = сш — любой символ из реферата присутствует на клавиатуре.

ФОРМАТ ВЫВОДА

Выведите единственное целое число — разнорядность заданной во входных данных
конструкции клавиатуры на реферате 5.

Пример1

Кликните здесь для просмотра всего текста

Ввод:
4
1 2 3 4
1 2 1 2
5
1 2 3 1 4
Вывод:
4

Пример2

Кликните здесь для просмотра всего текста

Ввод:
3
42 3 14
1 3 3
4
3 14 14 3
Вывод:
0

Теперь касаемо моего решения и мыслей по задаче. Я понял, что по факту здесь у нас считаются перескоки по клавиатуре(которая описывается строчками 2 и 3) в зависимости от строчки под номером 5. Поскольку строчка 5 - это то, что мы хотим написать, то логично, что и нажатий на клаву(и возможных переходов по строкам клавиатуры) у нас столько же, сколько и чисел в 5ой строке. Поэтому я решил на основании 5ой строки и 2 и 3-ей сделать по сути массив флагов-переходов с одной строчки на другую. Если у нас эти флаги отличаются, значит произошел переход и надо счетчику прибавить 1.

То есть на примере входных данных с примера 1 у меня строка "1 2 3 1 4" превращается в строку "1 2 1 1 2" (от есть мы идем по цифрам в строке 5 и сопоставляем каждое число с числом из строки 2 и подставляем его позицию из строки 3). Далее мы идем по строке "1 2 1 1 2" и считаем количество переходов вот по такой логике:

1->2

2->1

1->1

1->2

Итого ответ 3.

К сожалению такое мое решение прошло 15 тестов из N имеющихся и в ошибке мне вывели лог о том, что превышено время выполнения. Так и не смог понять в чем дело, на этом мой отбор на стажу и закончился. Но задачу я дорешать просто обязан, ибо она мне спать не дает). Поэтому максимально подробно изложил свои мысли по решению и ниже прикрепил код на С++. Надеюсь на конструктивную критику и любые годные мысли по данному вопросу. Всем спасибо, всем добра

C++Выделить код

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <iostream>
using namespace std;
 
int main() {
    int sizeArray1, sizeArray3;
 
    cin >> sizeArray1;
    int arr1 = new int[sizeArray1];
    int arr2 = new int[sizeArray1];
 
    for(int i = 0; i < sizeArray1; i++) {
        cin >> arr1[i];
    }
 
    for(int i = 0; i < sizeArray1; i++) {
        cin >> arr2[i];
    }
 
    cin >> sizeArray3;
    int arr3 = new int[sizeArray3];
    int newArr = new int[sizeArray3];
 
    for(int i = 0; i < sizeArray3; i++) {
        cin >> arr3[i];
    }
 
 
    cout << endl;
 
 
    int count = 0;
    for(size_t i = 0; i < sizeArray3; i++) {
        for(size_t j = 0; j < sizeArray1; j++) {
            if(arr3[i] == arr1[j]) {
                newArr[count] = arr2[j];
                count++;
                break;
            }
        }
    }
    int countElements = 0;
    for(size_t i = 1; i < count; i++) {
        if(newArr[i - 1] != newArr[i]) {
            countElements++;
        }
    }
    cout << countElements;
 
    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    delete[] newArr;
 
    return 0;
}

Добавлено через 1 минуту

Заранее перед всеми извиняюсь за не самое красивое форматирование сообщения. К сожалению не очень хорошо пользуюсь таблицами, спойлерами и прочими инструментами форума