4c-saruman.js

/*

C. Саруман

Ограничение времени	4 секунды (фактическое использование на тестах – до 3.006s)
Ограничение памяти	256Mb (фактическое использование на тестах – до 123.38Mb)
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Как известно, Саруман Радужный очень любит порядок. Поэтому все полки его войска стоят друг за другом, причем каждый следующий полк содержит количество орков не меньше, чем предыдущий.

Перед тем как напасть на Хельмову Падь, Саруман решил провести несколько вылазок для разведки. Чтобы его отряды никто не заметил, он решил каждый раз отправлять несколько подряд идущих полков так, чтобы суммарное количество орков в них было равно определенному числу. Так как это всего лишь разведка, каждый полк после вылазки возвращается на свое место. Задачу выбрать нужные полки он поручил Гриме Змеиному Языку. А Грима не поскупится на вознаграждение, если вы ему поможете.

Формат ввода
В первой строке входного файла находится два целых числа: n (1 ≤ n ≤ 2 ⋅ 10^5) — количество полков и m (1 ≤ m ≤ 2 ⋅ 10^5) – количество предстоящих вылазок.
В следующей строке записано n чисел a[i], где a[i] — число орков в i-ом полке (1 ≤ a[i] ≤ 10^9, a[i] ≤ a[i] + 1).
Далее в m строках записаны запросы вида: количество полков l (1 ≤ l ≤ n), которые должны будут отправиться в эту вылазку, и суммарное количество орков в этих полках s (1 ≤ s ≤ 2 ⋅ 10^16)

Формат вывода
Для каждого запроса выведите номер полка, с которого начнутся те l, которые необходимо отправить на вылазку. Если таких полков несколько, выведите любой. Если же так выбрать полки нельзя, выведите -1.

Пример

Ввод
5 2
1 3 5 7 9
2 4
1 3

Вывод
1
2

*/

const fs = require('fs');

const input = fs.readFileSync('input.txt', 'utf8').toString().trim().split('\n');

const regimentPrefixSum = new Array();
const dataString = input[1].trim() + ' ';
const length = dataString.length;

let valueString = '';
let valueCount = 0;

for (let pos = 0; pos < length; ++pos) {
    if (dataString[pos] === ' ') {
        const valueNumber = BigInt(valueString);
        if (valueCount === 0) {
            regimentPrefixSum[valueCount] = valueNumber;
        } else {
            regimentPrefixSum[valueCount] = valueNumber + regimentPrefixSum[valueCount - 1];
        }
        ++valueCount;
        valueString = '';
    } else {
        valueString += dataString[pos];
    }
}

let result = '';

for (let i = 2; i < input.length; ++i) {
    let [numberOfRegiments, totalForceSize] = input[i].trim().split(' ');
    numberOfRegiments = parseInt(numberOfRegiments);
    totalForceSize = BigInt(totalForceSize);

    let left = 0;
    let right = regimentPrefixSum.length - 1;
    let middle = 0;
    let size = 0n;

    while (left < right) {
        middle = Math.floor((left + right) / 2);
        size = regimentPrefixSum[middle] - (regimentPrefixSum[middle - numberOfRegiments] || 0n);
        if (totalForceSize <= size) {
            right = middle;
        } else {
            left = middle + 1;
        }
    }

    const index = left;
    size = regimentPrefixSum[index] - (regimentPrefixSum[index - numberOfRegiments] || 0n)
    if (size === totalForceSize) {
        result += `${index - numberOfRegiments + 2}\n`;
    } else {
        result += `-1\n`;  
    }
}

fs.writeFileSync('output.txt', `${result.trim()}`);