Что спрашивают

В журнале N оценок в порядке производства. Максимальная оценка единственна. Особенная деталь находится после неё, имеет оценку в [A; B] и отличается от следующей детали не более чем на K. Последняя запись не считается особенной.

Нужно вывести наивысшее место особенной детали и общее число особенных. Место оценки x равно 1 плюс число всех деталей с оценкой строго больше x. 3 < N < 100 000, оценки ≤ 1000; особенные есть.

Приём решения

Не сортируйте журнал до отбора: условие использует хронологическое соседство. Найдите индекс единственного максимума. Рассматривайте индексы от него плюс один до N - 2 включительно, чтобы у каждой детали была следующая.

Проверяйте A <= value <= B и abs(next_value - value) <= K. Считайте все подходящие детали, а среди их оценок запоминайте наибольшую best. Более высокая оценка всегда означает не худшее место, поэтому только best нужна для первого ответа.

После отбора посчитайте по полному журналу число оценок, строго больших best, и прибавьте один. Повторяющиеся оценки выше best учитываются каждая: рейтинг обычный, с общими местами и пропусками, а не плотный рейтинг различных баллов.

Получаются линейные проходы, O(N) времени и O(N) памяти на журнал. Ограничение оценок 1000 позволяет использовать частоты, но для этого решения они не нужны.

Разбор на примере

Ввод

9
50 80 4
78
99
60
63
61
70
75
75
80

Вывод

4 3
Разбор примера по шагам
Оценка после максимумаРазница со следующейОсобенная?
603Да
632Да
619Нет
705Нет
75, первая0Да
75, вторая5Нет
80Следующей нетНет

После 99 подходят оценки 60, 63 и первая из двух 75: следующие отличаются от них на 3, 2 и 0. Оценка 70 не подходит из-за разницы 5; вторая 75 тоже не подходит перед 80. Последняя 80 исключена. Лучшая особенная оценка 75; выше неё три детали с оценками 78, 99 и 80, значит место 4.

Код на Python и C++

Гарантия наличия особенных позволяет вычислять rank без отдельного ответа для пустого отбора. Равные best оценки не увеличивают место.

В C++ первую позицию наибольшей оценки даёт max_element, как values.index(max(values)) в Python.

import sys


def solve(a, b, k, values):
    peak = values.index(max(values))
    count = best = 0
    for i in range(peak + 1, len(values) - 1):
        if a <= values[i] <= b and abs(values[i + 1] - values[i]) <= k:
            count += 1
            best = max(best, values[i])
    rank = 1 + sum(value > best for value in values)
    return rank, count


if __name__ == '__main__':
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, a, b, k = data[:4]
    print(*solve(a, b, k, data[4:]))
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long a, b, k;
    cin >> n >> a >> b >> k;
    vector<long long> values(n);
    for (long long& value : values)
        cin >> value;
    int peak = max_element(values.begin(), values.end()) - values.begin();
    int count = 0;
    long long best = 0;
    for (int i = peak + 1; i < n - 1; i++) {
        if (a <= values[i] && values[i] <= b && llabs(values[i + 1] - values[i]) <= k) {
            count += 1;
            best = max(best, values[i]);
        }
    }
    int rank = 1;
    for (long long value : values)
        rank += value > best;
    cout << rank << ' ' << count << endl;
}

Типичные ошибки

  • Отсортировать до поиска особенных

    После сортировки меняются соседние детали и положение максимума. Отбор выполняется только по исходному журналу.

  • Посчитать различные оценки выше

    Место зависит от количества деталей. Две детали с одинаковым большим баллом сдвигают место на два.

  • Проверить разность без модуля

    Следующая оценка может быть как больше, так и меньше. Условие симметрично и включает разность ровно K.