Для тестов до 10 было достаточно повыписывать ответы на листочке.

Для второй группы можно было перебрать все возможные пары $$$i$$$, $$$j$$$ и проверить выполнение условия. $$$O(n^2)$$$

Для третьей группы нужно было понять, что для фиксированного $$$i$$$ $$$j = n - i$$$. $$$O(n)$$$

Для полного решения заметим, что для каждого числа от $$$0$$$ до $$$n$$$ мы сможем найти пару. Тогда ответ это $$$n + 1$$$. Итоговая асимптотика $$$O(1)$$$.

#include <bits/extc++.h>
#define int int64_t

using namespace std;

int32_t main() {
      int n;
      scanf("%lld", &n);
      n++;
      printf("%lld", n);
}

Для первой группы было достаточно заметить, что ответ всегда равен $$$k$$$.

Для второй группы необходимо было найти количество единиц и двоек и решить аналогично первому случаю.

Для третьей группы необходимо было уметь искать минимум в массиве.

Для четвёртой группы можно было отсортировать массив за $$$O(n^2)$$$ (например, сортировкой пузырьком) и вывести сумму $$$k$$$ первых элементов.

Для полного решения просто отсортируем массив сортировкой за $$$O(n \log(n))$$$ (своей либо встроенной в ваш язык программирования).

#include<bits/stdc++.h>
#define int int64_t

using namespace std;

int32_t main(){
    int n, k;
    cin >> n >> k;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    int s = 0;
    for (int i = 0; i < k; i++)
        s += a[i];
    cout << s;
}

Для первой группы было достаточно разобрать тесты вручную.

Для второй группы можно было выводить сам ответ, а не остаток от деления.

Для третьей группы тестов можно было написать алгоритм, который был указан в условии. $$$O(n)$$$

Четвёртая группа тестов является большой подсказкой на полное решение. Просто выводим 0.

Для полного решения совместим обычный перебор из условия и отсечение на то, что $$$p \le n$$$. Асимптотика $$$O(min(p, n))$$$

#include <bits/extc++.h>
#define int int64_t

using namespace std;

int32_t main() {
      int n, p;
      cin >> n >> p;
      if (p <= n) {
            cout << 0;
            return 0;
      }
      int ans = 1;
      for (int i = n; i >= 1; i -= 2) {
            ans = ans * i % p;
      }
      cout << ans;
}

Для первой группы проверим то, что $$$|p| \le |s|$$$ ($$$|x|$$$ — длина строки $$$x$$$). Если условие выполняется, выведем $$$|p|$$$, иначе — $$$-1$$$.

Для второй группы можем использовать решение на первую подгруппу, но необходимо дополнительно проверить то, что $$$p$$$ состоит из одинаковых символов, причём таких же, как $$$s$$$.

Для третьей группы нужно было предпросчитать кол-во вхождений каждого символа на префиксе и с помощью этого ответить на запросы.

Для четвёртой группы нужно было уметь находить первое вхождение одного символа. Это можно было сделать, например, предпросчётом.

Для пятой группы мы можем написать проверку <<в лоб>>. $$$O(q \cdot n \cdot \log(n))$$$

Для полного решения необходимо было совместить предпросчёт из третьей группы и бинпоиск либо сохранение в предпросчёте индексов вхождений каждого символа, с помощью чего мы просто решаем задачу нахождения максимума из значений на позициях количества вхождений текущего символа в $$$|p|$$$. Асимптотика $$$O(q \cdot 26)$$$ либо $$$O(q \cdot \log(n) \cdot 26)$$$

#include <bits/extc++.h>
#define int int64_t

using namespace std;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> arr[26];
    for(int i = 0; i < n; i++) {
        arr[s[i] - 'a'].push_back(i + 1);
    }
    int q;
    cin >> q;
    while(q--) {
        int ptr[26]{};
        string nm;
        cin >> nm;
        int ans = 0;
        bool can = true;
        for(int i = 0; i < nm.size(); i++) {
            if (arr[nm[i] - 'a'].size() <= ptr[nm[i] - 'a']) {
                can = false;
                break;
            }
            ans = max(ans, arr[nm[i] - 'a'][ptr[nm[i] - 'a']]);
            ptr[nm[i] - 'a']++;
        }
        if (!can)
            cout << "-1\n";
        else
            cout << ans << '\n';
    }
}

Для первой группы ответ всегда $$$0$$$.

Для второй группы ответ может быть $$$1$$$, если существует $$$2$$$ левее $$$1$$$. Иначе ответ $$$0$$$.

Для третьей группы можно было перебрать все возможные подмножества. $$$O(2^n \cdot n)$$$

Есть несколько вариаций полного решения:

• Заметить, что так как ответ равен сумме разностей соседних в подмножестве, то этот ответ это $$$x - y$$$, где $$$x$$$ — самое левое, а $$$y$$$ — самое правое число подмножества. Далее мы можем находить либо перебором $$$O(n^2)$$$, 60 баллов, либо заметить, что нам фактически надо для фиксированного $$$y$$$ просто поддерживать максимум на префиксе, что умеют делать префиксные суммы.

• Решить методом динамического программирования. $$$dp_i$$$ — ответ для обработанного префикса $$$i$$$. $$$dp_i = \max_{j \lt i}(dp_j + a_i - a_j)$$$. Получаем решение за $$$O(n^2)$$$, в котором можно было заметить, что $$$a_i$$$ не меняется при изменении $$$j$$$, а поэтому необходимо просто знать максимум на префиксе от $$$dp_j + a_j$$$, что делается аналогично префиксными суммами.

#include<bits/stdc++.h>
#define int int64_t

using namespace std;

int32_t main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int mn = INT_MAX, ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, a[i] - mn);
        mn = min(mn, a[i]);
    }
    cout << ans;
}

Для первых трёх групп было достаточно написать то, что просят в условии <<в лоб>> (добавляя в set и проверяя, что его размер < r — l + 1). $$$O(q \cdot n \cdot \log(n))$$$

Для четвёртой группы подойдёт всё то же решение, но set слишком медленный, поэтому используем хеш-таблицу (unordered set либо gp hash table). $$$O(q \cdot n)$$$

Для следующих двух групп было достаточно решения на четвёртую подгруппу, но ещё необходимо было останавливать алгоритм, как только мы нашли ответ. $$$O(q \cdot min(n, A))$$$.

Для следующей группы необходимо было решать задачу оффлайн: отсортировать запросы в порядке алгоритма Мо и решать задачу с помощью него. Подробнее можете прочитать здесь: https://ru.algorithmica.org/cs/decomposition/mo. $$$O((q + n) \cdot \sqrt n)$$$

Для полного решения необходимо было заметить такой факт:

Давайте для каждого индекса $$$i$$$ найдём такой индекс $$$j$$$, что $$$j \lt i$$$, $$$a_i = a_j$$$ и $$$|j - i|$$$ минимален. Если такого $$$j$$$ не существует, положим его значение $$$-1$$$. Тогда несложно заметить, что ответ на запрос это проверка на то, что максимум на отрезке $$$[l, r]$$$ в полученном массиве $$$\ge l$$$.

Теперь данную задачу можно решить на 80 баллов обычным деревом отрезков (рекурсивное дерево заходит наравне с нерекурсивным).

Для решения на 100 необходимо было также заметить, что вы на самом деле можете отвечать на запросы не $$$max(l, r) \ge l$$$, а $$$max(0, r) \ge l$$$, потому что отрезок $$$[0, l - 1]$$$ никак не влияет на ответ (максимальное значение там могло быть $$$l - 2$$$). Теперь задача свелась к максимуму на префиксе, что решается обычными префиксными максимумами.

#include<bits/stdc++.h>

using namespace std;

const int N = 2e6 + 5e5 + 1;
const int A = 5e6 + 1;

int n, q;
int a[N];
int last[A];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        int cur = a[i];
        a[i] = max(a[i - 1], last[cur]);
        last[cur] = i;
    }
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << (a[r] >= l ? "Yes\n" : "No\n");
    }
}

Для решения первой подгруппы было достаточно написать то, что написано в условии. Просто переберём все пары и проверим выполнение условия.

Для второй подгруппы повыписываем количество пар для фиксированного $$$i$$$. Заметим, что нестандартное ограничение по $$$j$$$, а также ограничение в виде $$$i$$$ and $$$j = i$$$ позволяет нам заметить то, что количество возможных пар зависит от количества нулевых битов в числе, а именно, для фиксированного $$$i$$$ количество пар равно $$$2^{bit}$$$, где $$$bit = $$$ кол-во нулевых битов.

Для третьей подгруппы достаточно было написать стандартное решение динамическим программированием по цифрам.

Для четвёртой подгруппы заметим следующий факт: разобьём $$$i$$$ на группы $$$[2^k; 2^{k + 1} - 1]$$$. В каждой группе сумма равняется $$$3^{k}$$$.

Для полного решения повыписываем несколько первых ответов для фиксированного $$$i$$$: 1 2 1 4 2 2 1. Заметим некую симметричность в каждой группе, описанной в предыдущем пункте. А именно, если разбить такую группу на две, то сумма в первой половине равна $$$\frac{2}{3}$$$ от суммы группы, а во второй половине $$$\frac{1}{3}$$$ от суммы соответственно. Если продолжать такой спуск, то зависимость сохраняется.

Первая идея полного решения: Давайте решим задачу с помощью длинной арифметики: для младших битов просуммируем геометрическую прогрессию, для старшего сделаем спуск с проверкой на то, что число <= искомой середины. Далее, если спускаемся в левую половину, просто делаем $$$sum := \frac{2}{3} sum$$$. Иначе прибавляем эти $$$\frac{2}{3} sum$$$, $$$sum := \frac{1}{3} sum$$$.

Для более простого решения достаточно было заметить, что число нам задано в двоичной системе счисления. Тогда просто проверка на <= это проверка на значение $$$0 / 1$$$ текущего бита. С одним отличием. Спуск по битам проверяет на <, а не на <=. Для того, чтобы это исправить, просто увеличим исходное число на единицу, что несложно реализуется в двоичной системе.

#include <bits/extc++.h>

#define int int64_t

using namespace std;

const int mod = 1e9 + 7;

int binpow(int x, int y) {
    if (y == 0)
        return 1;
    if (y & 1)
        return binpow(x, y - 1) * x % mod;
    int z = binpow(x, y / 2);
    return z * z % mod;
}

int add(int x, int y) {
    return (x + y + mod) % mod;
}

int mul(int x, int y) {
    return x * y % mod;
}

int divd(int x, int y) {
    return mul(x, binpow(y, mod - 2));
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string l;
    cin >> l;
    int cnt = 0;
    while (!l.empty() && l.back() == '1')
        l.pop_back(), cnt++;
    if (!l.empty())
        l.pop_back();
    l.push_back('1');
    while (cnt--)
        l.push_back('0');
    int ans = 0, cur = 1;
    for (int i = 0; i + 1 < l.size(); i++) {
        ans = add(ans, cur);
        cur = mul(cur, 3);
    }
    for (int i = 1; i < l.size(); i++) {
        if (l[i] == '1') {
            ans = add(ans, mul(divd(cur, 3), 2));
            cur = divd(cur, 3);
        }
        else
            cur = mul(divd(cur, 3), 2);
    }
    cout << ans;
}