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.

3

9 1 10
-6 +1 +2 +3 -4 *3 -5 @1 -5
10
1
2
3
4
5
6
7
8
9
10

6 1 10
-6 +1 +2 +3 -4 *3
10
1
2
3
4
5
6
7
8
9
10

2 20 25
+20 -1
1
3

36
93
22

Don't submit your code until you believe that significant optimization over MMM's solution has been achieved.
MMM's solution would run for an hour on our test data but we expect your solution to finish within seconds.

2013 Asia Regional Changchun