Cerinta completa

Given an array of integers, you must answer a number of queries. Each query consists of a single integer, , and is performed as follows:

  1. Add to each element of the array, permanently modifying it for any future queries.
  2. Find the absolute value of each element in the array and print the sum of the absolute values on a new line.

Tip: The Input/Output for this challenge is very large, so you’ll have to be creative in your approach to pass all test cases.

Function Description

Complete the playingWithNumbers function in the editor below. It should return an array of integers that represent the responses to each query.

playingWithNumbers has the following parameter(s):

  • arr: an array of integers
  • queries: an array of integers

Input Format

The first line contains an integer the number of elements in .
The second line contains space-separated integers .
The third line contains an integer , the number of queries.
The fourth line contains space-separated integers where .

Constraints

  • , where .
  • , where

Output Format

For each query, print the sum of the absolute values of all the array’s elements on a new line.

Sample Input

3
-1 2 -3
3
1 -2 3

Sample Output

5
7
6

Explanation

Query 0:
Array:
The sum of the absolute values of the updated array’s elements is .

Query 1:
Array:
The sum of the absolute values of the updated array’s elements is .

Query 2:
Array:
The sum of the absolute values of the updated array’s elements is .

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;

public class Solution {
    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) {
            this.in = is;
        }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            int val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

    private static int lowerBound(int[] a, long target) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);

        int n = fs.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = fs.nextInt();
        Arrays.sort(arr);

        long[] pref = new long[n + 1];
        for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i];
        long total = pref[n];

        int q = fs.nextInt();
        long add = 0;

        StringBuilder out = new StringBuilder();
        for (int i = 0; i < q; i++) {
            add += fs.nextInt();

            int split = lowerBound(arr, -add);
            long leftCnt = split;
            long rightCnt = n - split;
            long leftSum = pref[split];
            long rightSum = total - leftSum;

            long ans = -(leftSum + add * leftCnt) + (rightSum + add * rightCnt);
            out.append(ans).append('\n');
        }

        String outputPath = System.getenv("OUTPUT_PATH");
        if (outputPath != null && !outputPath.isEmpty()) {
            try (BufferedWriter bw = new BufferedWriter(new FileWriter(outputPath))) {
                bw.write(out.toString());
            }
        } else {
            System.out.print(out);
        }
    }
}

Scor obtinut: 1.0

Submission ID: 464613981

Link challenge: https://www.hackerrank.com/challenges/playing-with-numbers/problem

Absolute Element Sums