I finally solved this problem. Everytime I see the word queries or MOD 1000000007 I instantly panic because I know I haven’t quite yet gotten to making a Segment Tree or solving DP problems yet. I did end up making a Segment Tree that does successfully solve this problem however since our input is so huge it will most definitely TLE. Here is my solution, I can just keep summing the values and put them in an ArrayList and then just compare the sums at the query endpoints. I did however miss out the edge case of [1,0,0,0,0] as the sum would be same at both ends however the actual numbers are different. I just added that case in and AC!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
/**
*
* @author Sanchit M. Bhatnagar
* @see http://uhunt.felix-halim.net/id/74004
*
*/
public class P10324 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
StringTokenizer st = null;
long test = 1;
String line = null;
while ((line = br.readLine()) != null) {
char[] input = line.trim().toCharArray();
if (input.length == 0)
break;
ArrayList<Integer> sumArray = new ArrayList<Integer>();
int sum = 0;
for (int i = 0; i < input.length; i++) {
sum += Integer.parseInt(input[i] + "");
sumArray.add(sum);
}
int N = Integer.parseInt(br.readLine().trim());
out.println("Case " + test + ":");
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
out.println(solve(Math.min(a, b), Math.max(a, b), sumArray, input));
}
test++;
}
out.close();
br.close();
}
private static String solve(int min, int max, ArrayList<Integer> sumArray, char[] input) {
int a = sumArray.get(min);
int b = sumArray.get(max);
if ((a == b || b - a + 1 == max - min + 1) && input[min] == input[max]) {
return "Yes";
} else {
return "No";
}
}
}

### Like this:

Like Loading...