4817：Min-max-multiply

MMM is solving a problem on an online judge, but her solution got TLE (Time limit exceeded). Here is her submitted Java solution:

public class PleaseUseProperClassNameAccordingToYourContestEnvironment {
  private static Scanner cin;
  private static int n;
  private static char[] command;
  private static long[] arr;
  private static long minValue, maxValue;
  public static void read() {
    n = cin.nextInt();
    minValue = cin.nextLong();
    maxValue = cin.nextLong();
    command = new char[n];
    arr = new long[n];
    cin.nextLine();
    String[] tokens = cin.nextLine().split(" ");
    for (int i = 0; i < n; i++) {
      command[i] = tokens[i].charAt(0);
      arr[i] = Long.valueOf(tokens[i].substring(1));
    }
  }

  public static void go() {
    int numQuery = cin.nextInt();
    long ans = 0;
    long y, y0;
    for (int i = 0; i < numQuery; i++) {
      y0 = cin.nextLong();
      y = y0;
      for (int j = 0; j < n; ++j) {
        switch (command[j]) {
          case '+':
            y += arr[j];
            break;
          case '-':
            y -= arr[j];
            break;
          case '*':
            y *= arr[j];
            break;
          case '@':
            y += y0 * arr[j];
        }
        y = Math.min(maxValue, y);
        y = Math.max(minValue, y);
      }
      ans += y;
    }
    System.out.println(ans);
  }

  public static void main(String argv[]) throws IOException {
    cin = new Scanner(System.in);
    int numTest = cin.nextInt();
    while (numTest-- > 0) {
      read();
      go();
    }
  }
}

She thought that maybe this is due to the slowness of Java compared to C++. So she changed her program into C++, however, she got TLE again:

const int kMaxN = 1000000;
char command[kMaxN];
long long arr[kMaxN];
int main() {
  int num_case = 0;
  scanf("%d", &num_case);
  assert(1 <= num_case && num_case <= 10);
  for (int icase = 0; icase < num_case; ++icase) {
    int n;
    long long min_value, max_value;
    scanf("%d%lld%lld", &n, &min_value, &max_value);
    assert(1 <= n && n <= 1000000);
    assert(1 <= min_value && min_value <= max_value);
    assert(max_value <= 10000000000LL); // 10^10
    for (int i = 0; i < n; ++i) {
      scanf(" %c%lld", command + i, arr + i);
      assert(1 <= arr[i] && arr[i] <= 10000000000LL); // 10^10
      if (command[i] == '*' || command[i] == '@') {
        assert(arr[i] <= 100000); // 10^5
      }
    }
    int num_query;
    scanf("%d", &num_query);
    assert(num_query <= 1000000);
    long long ans = 0;
    for (int iquery = 0; iquery < num_query; ++iquery) {
      long long start_value;
      scanf("%lld", &start_value);
      assert(1 <= start_value && start_value <= 10000000000LL); // 10^10
      long long sum = start_value;
      for (int i = 0; i < n; ++i) {
        switch(command[i]) {
          case '+':
            sum += arr[i];
            break;
          case '-':
            sum -= arr[i];
            break;
          case '@':
            sum += start_value * arr[i];
            break;
          default:
            assert(command[i] == '*');
            sum *= arr[i];
        }
        sum = min(sum, max_value);
        sum = max(sum, min_value);
      }
      ans += sum;
    }
    printf("%lld\n", ans);
  }
  return 0;
}

MMM was so desperate that she asked the judge for help. The judge found out that both programs produce the correct output; however, they cannot finish execution within the time limit. Could you, our talented contestant, help her optimize the algorithm and got AC?

The first line of input is an integer T (0 < T ≤ 100) indicating the number of test cases.

For each case, there are 3 integers n, min_value, max_value in the first line, which denote the number of operations, the minimum and maximum value after each operation, respectively (1 ≤ n ≤ 10^6, 1 ≤ min_value ≤ max_value ≤ 10^10).

Then there are n operations in the next line. Each operation is an operator, '+', '-', '@' or '*', followed by a positive integer, without any spaces between them.

For operations of format +x and -x, you can assume 1 ≤ x ≤ 10^10.

And for operations of format *x and @x, you can assume 1 ≤ x ≤ 10^5.

After the line of operations, there would be an integer num_query indicating the number of queries (1 ≤ num_query ≤ 10^6).

Then num_query integers x_i follows, each of them is of range 1 ≤ x_i ≤ 10^10

For each case, output num_query numbers. Please refer to the problem statement for the meaning of the result.