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"; } } }