Problem Description
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?
Input
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
Output
For each case, output num_query numbers. Please refer to the problem statement for the meaning of the result.
Sample Input
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
Sample Output
36
93
22
