HARDAtCoderLiveCodeBenchFail → Pass

LCB-01: Best Performances

Baseline: FAIL
Augmented: PASS
Injection: 2,414 chars

The Task

We have a sequence A=(A_1,A_2,\dots,A_N) of length N. Initially, all the terms are 0. Using an integer K given in the input, we define a function f(A) as follows: - Let B be the sequence obtained by sorting A in descending order (so that it becomes monotonically non-increasing). - Then, let f(A)=B_1 + B_2 + \dots + B_K. We consider applying Q updates on this sequence. Apply the following operation on the sequence A for i=1,2,\dots,Q in this order, and print the value f(A) at that point after each update. - Change A_{X_i} to Y_i. Input The input is given from Standard Input in the following format: N K Q X_1 Y_1 X_2 Y_2 \vdots X_Q Y_Q Output Print Q lines in total. The i-th line should contain the value f(A) as an integer when the i-th update has ended. Constraints - All input values are integers. - 1 \le K \le N \le 5 \times 10^5 - 1 \le Q \le 5 \times 10^5 - 1 \le X_i \le N - 0 \le Y_i \le 10^9 Sample Input 1 4 2 10 1 5 2 1 3 3 4 2 2 10 1 0 4 0 3 1 2 0 3 0 Sample Output 1 5 6 8 8 15 13 13 11 1 0 In this input, N=4 and K=2. Q=10 updates are applied. - The 1-st update makes A=(5, 0,0,0). Now, f(A)=5. - The 2-nd update makes A=(5, 1,0,0). Now, f(A)=6. - The 3-rd update makes A=(5, 1,3,0). Now, f(A)=8. - The 4-th update makes A=(5, 1,3,2). Now, f(A)=8. - The 5-th update makes A=(5,10,3,2). Now, f(A)=15. - The 6-th update makes A=(0,10,3,2). Now, f(A)=13. - The 7-th update makes A=(0,10,3,0). Now, f(A)=13. - The 8-th update makes A=(0,10,1,0). Now, f(A)=11. - The 9-th update makes A=(0, 0,1,0). Now, f(A)=1. - The 10-th update makes A=(0, 0,0,0). Now, f(A)=0.

Scroll to read full problem statement

The Code

Claude Opus 4.6 with max-effort extended thinking. Exact outputs. Side by side.

Baseline

FAIL0ch / 610s
// No code produced (timeout)

Scroll to read full code

Augmented

PASS1464ch / 495s
import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1

    qx = []
    qy = []
    for _ in range(Q):
        qx.append(int(data[idx])); idx += 1
        qy.append(int(data[idx])); idx += 1

    vals = sorted(set(qy + [0]))
    M = len(vals)
    vm = {v: i + 1 for i, v in enumerate(vals)}

    LOG = M.bit_length()
    pows = [1 << k for k in range(LOG - 1, -1, -1)]

    cnt = [0] * (M + 2)
    sm = [0] * (M + 2)

    j = vm[0]
    while j <= M:
        cnt[j] += N
        j += j & (-j)

    A = [0] * (N + 1)
    tot = 0
    R = N - K

    out = []
    ap = out.append

    for i in range(Q):
        x = qx[i]
        nv = qy[i]
        ov = A[x]
        A[x] = nv

        j = vm[ov]
        while j <= M:
            cnt[j] -= 1
            sm[j] -= ov
            j += j & (-j)

        j = vm[nv]
        while j <= M:
            cnt[j] += 1
            sm[j] += nv
            j += j & (-j)

        tot += nv - ov

        if R == 0:
            ap(tot)
        else:
            pos = 0
            rem = R
            sb = 0
            for pw in pows:
                npos = pos + pw
                if npos <= M and cnt[npos] < rem:
                    rem -= cnt[npos]
                    sb += sm[npos]
                    pos = npos
            ap(tot - sb - rem * vals[pos])

    print('\n'.join(map(str, out)))

main()

Scroll to read full code

Blind Evaluation

Independent evaluator. Randomized A/B labels. No knowledge of which solution used the injection.

Solo evaluation: 35/50

DimensionScore
Correctness9
Efficiency9
Code Structure5
Readability4
Robustness8
Blind Analysis

The solution computes f(A) (sum of top K elements) via a complementary reformulation: instead of tracking the top K, it computes total_sum - sum_of_bottom_(N-K)_elements. This is the pivotal insight that makes the entire approach work. Coordinate compression maps all possible values to contiguous 1-indexed positions, bounding the BIT size to O(Q). Two Fenwick trees store counts and value sums. BIT binary lifting finds the boundary value in O(log M) time.

Blind Observation

The defining characteristic of this solution is one non-obvious reformulation that collapses the problem's complexity. Computing "sum of top K" directly requires maintaining a dynamic sorted structure with partial-sum queries — a design space full of tricky edge cases around the K-th boundary. Reframing as "total minus sum of bottom N-K" converts it into a standard k-th-smallest problem on a Fenwick tree, a well-documented competitive programming primitive.

Source: LiveCodeBench Hard benchmark. Full code outputs: baseline · augmented · runner script & methodology

Back to Use CasesStart Building