Défi · traitement de données difficile JavaScript ·

Range add, range sum

/**
 * @param {number[]} nums
 * @param {Array[]} ops
 * @returns {number[]}
 */
function range_add_sum(nums, ops)

range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])  // -> [10, 13, 17]
range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])  // -> [0]

• #1Google Gemini 3.8 Flashrésolu · 10 sur 10 testsréponse en 5.2 s · exécution 544 ms · $0.0032

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])attendu [10, 13, 17]	3 ms
  ✓	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])attendu [0]	1 ms

  ✓ 2 ms✓ <1 ms✓ 25 ms✓ 2 ms✓ 2 ms✓ 1 ms⏱ 360 ms⏱ 147 ms
  Code

  /**
   * @param {number[]} nums
   * @param {Array[]} ops
   * @returns {number[]}
   */
  function range_add_sum(nums, ops) {
    const n = nums.length;
    if (n === 0) return [];
  
    // Binary Indexed Tree (Fenwick tree) with range updates and range queries
    // Maintains: A[i] = nums[i] initially, plus updates.
    // sum(0..i) = (sum(B1, i) * (i + 1)) - sum(B2, i)
    // To add v to [l, r]:
    // add(B1, l, v), add(B1, r + 1, -v)
    // add(B2, l, v * l), add(B2, r + 1, -v * (r + 1))
  
    const b1 = new Float64Array(n + 2);
    const b2 = new Float64Array(n + 2);
  
    function bitAdd(idx, v) {
      const vIdx = v * idx;
      for (let i = idx + 1; i <= n; i += i & -i) {
        b1[i] += v;
        b2[i] += vIdx;
      }
    }
  
    function rangeAdd(l, r, v) {
      bitAdd(l, v);
      // For r + 1:
      const idx2 = r + 1;
      const v2 = -v;
      const vIdx2 = v2 * idx2;
      for (let i = idx2 + 1; i <= n; i += i & -i) {
        b1[i] += v2;
        b2[i] += vIdx2;
      }
    }
  
    function prefixSum(idx) {
      if (idx < 0) return 0;
      let s1 = 0;
      let s2 = 0;
      for (let i = idx + 1; i > 0; i -= i & -i) {
        s1 += b1[i];
        s2 += b2[i];
      }
      return s1 * (idx + 1) - s2;
    }
  
    // Precompute initial prefix sums of nums to avoid N updates
    const pref = new Float64Array(n + 1);
    for (let i = 0; i < n; i++) {
      pref[i + 1] = pref[i] + nums[i];
    }
  
    const results = [];
    const len = ops.length;
    for (let i = 0; i < len; i++) {
      const op = ops[i];
      if (op[0] === 'add') {
        rangeAdd(op[1], op[2], op[3]);
      } else {
        const l = op[1];
        const r = op[2];
        const initialSum = pref[r + 1] - pref[l];
        const addedSum = prefixSum(r) - prefixSum(l - 1);
        results.push(initialSum + addedSum);
      }
    }
  
    return results;
  }

• #2DeepSeek V4.1 Flashrésolu · 10 sur 10 testsréponse en 1.5 s · exécution 1.3 s · $0.0005

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])attendu [10, 13, 17]	2 ms
  ✓	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])attendu [0]	1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ 2 ms⏱ 727 ms⏱ 578 ms
  Code

  function range_add_sum(nums, ops) {
    const n = nums.length;
    const size = 1 << Math.ceil(Math.log2(n || 1));
    const sum = new Float64Array(2 * size);
    const lazy = new Float64Array(2 * size);
  
    for (let i = 0; i < n; i++) sum[size + i] = nums[i];
    for (let i = size - 1; i > 0; i--) sum[i] = sum[2 * i] + sum[2 * i + 1];
  
    function apply(node, l, r, v) {
      sum[node] += v * (r - l + 1);
      lazy[node] += v;
    }
  
    function push(node, l, r) {
      const v = lazy[node];
      if (v !== 0) {
        const mid = (l + r) >> 1;
        apply(2 * node, l, mid, v);
        apply(2 * node + 1, mid + 1, r, v);
        lazy[node] = 0;
      }
    }
  
    function update(node, l, r, ql, qr, v) {
      if (ql > r || qr < l) return;
      if (ql <= l && r <= qr) {
        apply(node, l, r, v);
        return;
      }
      push(node, l, r);
      const mid = (l + r) >> 1;
      update(2 * node, l, mid, ql, qr, v);
      update(2 * node + 1, mid + 1, r, ql, qr, v);
      sum[node] = sum[2 * node] + sum[2 * node + 1];
    }
  
    function query(node, l, r, ql, qr) {
      if (ql > r || qr < l) return 0;
      if (ql <= l && r <= qr) return sum[node];
      push(node, l, r);
      const mid = (l + r) >> 1;
      return query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr);
    }
  
    const res = [];
    for (let i = 0; i < ops.length; i++) {
      const op = ops[i];
      if (op[0] === "add") {
        update(1, 0, size - 1, op[1], op[2], op[3]);
      } else {
        res.push(query(1, 0, size - 1, op[1], op[2]));
      }
    }
    return res;
  }

• #3OpenAI GPT-6 Lunanon résolu · 4 sur 10 testsréponse en 4.1 s · exécution 1.9 s · $0.0003

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])attendu [10, 13, 17]	3 ms
  ✗	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])attendu [0]obtenu [-5]	<1 ms

  ✓ <1 ms✓ 3 ms✗ mauvaise réponse✓ 1 ms✗ mauvaise réponse✗ mauvaise réponse⏱ mauvaise réponse⏱ mauvaise réponse
  Code

  function range_add_sum(nums, ops) {
    const n = nums.length;
    const size = Math.ceil(Math.sqrt(n));
    const blocks = Math.ceil(n / size);
    const sums = new Float64Array(blocks);
    const lazy = new Float64Array(blocks);
  
    for (let i = 0; i < n; i++) sums[Math.floor(i / size)] += nums[i];
  
    function prefix(end) {
      let total = 0;
      let i = 0;
      while (i <= end) {
        const b = Math.floor(i / size);
        const blockEnd = Math.min(n - 1, (b + 1) * size - 1);
        if (i === b * size && blockEnd <= end) {
          total += sums[b] + lazy[b] * (blockEnd - i + 1);
          i = blockEnd + 1;
        } else {
          total += nums[i] + lazy[b];
          i++;
        }
      }
      return total;
    }
  
    const result = [];
    for (const op of ops) {
      const l = op[1], r = op[2];
      if (op[0] === "sum") {
        result.push(prefix(r) - (l ? prefix(l - 1) : 0));
        continue;
      }
  
      const v = op[3];
      let i = l;
      while (i <= r) {
        const b = Math.floor(i / size);
        const blockEnd = Math.min(n - 1, (b + 1) * size - 1);
        if (i === b * size && blockEnd <= r) {
          sums[b] += v * (blockEnd - i + 1);
          lazy[b] += v;
          i = blockEnd + 1;
        } else {
          nums[i] += v;
          sums[b] += v;
          i++;
        }
      }
    }
    return result;
  }

  Second essai

  non résolu · 5 sur 10 testsréponse en 3.4 s · $0.0003

  Le modèle a eu accès au nombre de tests échoués, aux exemples en échec avec les valeurs attendues et obtenues, ainsi qu'au motif d'échec des tests cachés (sans leurs entrées). Ne compte ni pour le classement ni pour l'évaluation.

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])attendu [10, 13, 17]	2 ms
  ✗	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])attendu [0]obtenu [-5]	<1 ms

  ✓ 2 ms✓ 4 ms✗ mauvaise réponse✓ <1 ms✓ <1 ms✗ mauvaise réponse⏱ mauvaise réponse⏱ mauvaise réponse

  Code

  function range_add_sum(nums, ops) {
    const n = nums.length;
    const size = Math.max(1, Math.ceil(Math.sqrt(n)));
    const blocks = Math.ceil(n / size);
    const sums = new Float64Array(blocks);
    const lazy = new Float64Array(blocks);
  
    for (let i = 0; i < n; i++) sums[Math.floor(i / size)] += nums[i];
  
    function rangeSum(l, r) {
      let total = 0;
      let i = l;
      while (i <= r) {
        const b = Math.floor(i / size);
        const start = b * size;
        const end = Math.min(n - 1, start + size - 1);
        if (i === start && end <= r) {
          total += sums[b] + lazy[b] * (end - start + 1);
          i = end + 1;
        } else {
          total += nums[i] + lazy[b];
          i++;
        }
      }
      return total;
    }
  
    const result = [];
    for (const op of ops) {
      const l = op[1], r = op[2];
      if (op[0] === "sum") {
        result.push(rangeSum(l, r));
      } else {
        const v = op[3];
        let i = l;
        while (i <= r) {
          const b = Math.floor(i / size);
          const start = b * size;
          const end = Math.min(n - 1, start + size - 1);
          if (i === start && end <= r) {
            sums[b] += v * (end - start + 1);
            lazy[b] += v;
            i = end + 1;
          } else {
            nums[i] += v;
            sums[b] += v;
            i++;
          }
        }
      }
    }
    return result;
  }

• #4MoonshotAI Kimi K2.7 Codenon résolu · 0 sur 10 testsréponse en 53 s · exécution <1 ms · $0.02

  SyntaxError: Unexpected token ';'

  ✗	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])attendu [10, 13, 17]SyntaxError: Unexpected token ';'	—
  ✗	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])attendu [0]SyntaxError: Unexpected token ';'	—

  ✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError✗ SyntaxError⏱ SyntaxError⏱ SyntaxError
  Code

  /**
   * @param {number[]} nums
   * @param {Array[]} ops
   * @returns {number[]}
   */
  function range_add_sum(nums, ops) {
      const n = nums.length;
      const ans = [];
      if (n === 0) return ans;
  
      const size = n + 5; // extra room for r+1 updates
      const b1 = new Array(size).fill(0);
      const b2 = new Array(size).fill(0);
  
      function add(bit, idx, val) {
          for (let i = idx; i < size; i += i & -i) {
              bit[i] += val;
          }
      }
  
      function sum(bit, idx) {
          let s = 0;
          for (let i = idx; i > 0; i -= i & -i) {
              s += bit[i];
          }
          return s;
      }
  
      function rangeAdd(l, r, v) {
          add(b1, l, v);
          add(b1, r + 1, -v);
          add(b2, l, v * (l - 1));
          add(b2, r + 1, -v * r);
      }
  
      function prefix(idx) {
          return sum(b1, idx) * idx - sum(b2, idx);
      }
  
      function rangeSum(l, r) {
          return prefix(r) - prefix(l - 1);
      }
  
      // initialize with the original array values
      for (let i =

  Second essai

  résolu · 10 sur 10 testsréponse en 16 s · $0.0035

  Le modèle a eu accès au nombre de tests échoués, aux exemples en échec avec les valeurs attendues et obtenues, ainsi qu'au motif d'échec des tests cachés (sans leurs entrées). Ne compte ni pour le classement ni pour l'évaluation.

  ✓	range_add_sum([1, 2, 3, 4], [["sum", 0, 3], ["add", 1, 2, 10], ["sum", 0, 1], ["sum", 2, 3]])attendu [10, 13, 17]	2 ms
  ✓	range_add_sum([5], [["add", 0, 0, -5], ["sum", 0, 0]])attendu [0]	1 ms

  ✓ 3 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ <1 ms✓ <1 ms⏱ 359 ms⏱ 455 ms

  Code

  /**
   * @param {number[]} nums
   * @param {Array[]} ops
   * @returns {number[]}
   */
  function range_add_sum(nums, ops) {
      const n = nums.length;
      const ans = [];
      if (n === 0) return ans;
  
      const size = n + 5;
      const b1 = new Array(size).fill(0);
      const b2 = new Array(size).fill(0);
  
      function add(bit, idx, val) {
          for (let i = idx; i < size; i += i & -i) {
              bit[i] += val;
          }
      }
  
      function sum(bit, idx) {
          let s = 0;
          for (let i = idx; i > 0; i -= i & -i) {
              s += bit[i];
          }
          return s;
      }
  
      function rangeAdd(l, r, v) {
          l++;
          r++;
          add(b1, l, v);
          add(b1, r + 1, -v);
          add(b2, l, v * (l - 1));
          add(b2, r + 1, -v * r);
      }
  
      function prefix(idx) {
          return sum(b1, idx) * idx - sum(b2, idx);
      }
  
      function rangeSum(l, r) {
          return prefix(r + 1) - prefix(l);
      }
  
      for (let i = 0; i < n; i++) {
          rangeAdd(i, i, nums[i]);
      }
  
      for (let i = 0; i < ops.length; i++) {
          const op = ops[i];
          if (op[0] === "add") {
              rangeAdd(op[1], op[2], op[3]);
          } else {
              ans.push(rangeSum(op[1], op[2]));
          }
      }
  
      return ans;
  }

Coût en jetons: $0.02 · Déroulement et calcul des scores →