Submission #67333998

---

Source Code Expand

/**
 * ソートされた配列に対して二分探索を行い、結果の要素を返す。
 * @param {any[]} array - compareFnによってソートされた配列
 * @param {any} target - 探索対象の値
 * @param {(a: any, b: any) => number} [compareFn] - 比較関数。a < b の場合は負の値、a > b の場合は正の値、等しい場合は 0 を返す。
 * @param {boolean} [needEquality = false] - trueにした場合、配列にtargetと等しいと判定できる要素がない場合はundefinedを返すようになる。
 * @returns {any | undefined} - 探したい要素"以下"と判定されるもののうち最も後ろにある要素そのもの。(arrayの全要素がtargetより大きい場合はundefined、needEqualityがtrueかつtargetと等しい要素がない場合はundefined。)
 */
const bin_findLE = (array, target, compareFn = ((a, b) => { const [A, B] = [String(a), String(b)]; return (A < B) ? -1 : (A > B) ? 1 : 0 }), needEquality = false) => {
    if (array.length === 0) {
        return undefined;
    }

    let low = 0;
    let high = array.length - 1;
    let result = undefined;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (compareFn(array[mid], target) <= 0) {
            result = array[mid];
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    if (needEquality && result !== undefined && compareFn(result, target) !== 0) {
        return undefined;
    }

    return result;
}

function Main(inputText) {
    /** @type {String[][]} - スペース区切りと改行区切りをそのまま2次元配列に変えた状態 */
    const input = inputText.trim().split("\n").map(row => row.split(" "));
    /* ==== 本体 ==== */
    const Q = +input[0][0];
    const querys = [];
    // 入力受け取り
    for (let i = 1; i <= Q; i++) {
        if (+input[i][0] === 1) {
            querys.push({
                "type": 1,
                "c": +input[i][1],
                "x": +input[i][2]
            });
        }
        if (+input[i][0] === 2) {
            querys.push({
                "type": 2,
                "k": +input[i][1]
            });
        }
    }
    // どこまで削除したか持っておく
    let currentHead = 0;
    // どこの時点でいくつか覚えておく(2つ前→1つ前の差と違うところだけでOK)
    let currentTailIndex = -1;
    const sectionHeadIndexes = [];
    const sectionX = {};
    const sectionHead_A_acc = {};
    const getA_acc_i = (i) => {
        if (i < 0) return 0n;
        const latestHeadIndex = bin_findLE(sectionHeadIndexes, i, (a, b) => a - b);
        const A_acc_latestHeadIndex = sectionHead_A_acc[latestHeadIndex];
        const inSectionCount = i - latestHeadIndex;
        return A_acc_latestHeadIndex + BigInt(inSectionCount) * BigInt(sectionX[latestHeadIndex]);
    };
    // クエリ処理
    querys.forEach(query => {
        if (query.type === 1) {
            const c = query.c;
            const x = query.x;
            const sectionHeadIndex = currentTailIndex + 1;
            sectionHeadIndexes.push(sectionHeadIndex);
            sectionX[sectionHeadIndex] = x;
            sectionHead_A_acc[sectionHeadIndex] = getA_acc_i(currentTailIndex) + BigInt(x);
            currentTailIndex += c;
        }
        if (query.type === 2) {
            const k = query.k;
            const headIndex = currentHead;
            const tailIndex = currentHead + k - 1;
            console.log((getA_acc_i(tailIndex) - getA_acc_i(headIndex - 1)).toString());
            currentHead += k;
        }
    });
}
/* ==== これを書かないといけないらしい ==== */
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Submission Info

Judge Result