Skip to content

Instantly share code, notes, and snippets.

@tomerun
Created September 24, 2009 14:32
Show Gist options
  • Save tomerun/192761 to your computer and use it in GitHub Desktop.
Save tomerun/192761 to your computer and use it in GitHub Desktop.
import java.io.File;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class PKU3368 {
static ArrayList<Integer> ci;
static int[] max;
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(new File("bin/in.txt"));
// Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
StringBuilder output = new StringBuilder();
while (n > 0) {
int q = sc.nextInt();
max = new int[4 * n];
sc.nextLine();
String[] as = sc.nextLine().split(" ");
int prev = Integer.MIN_VALUE;
ci = new ArrayList<Integer>();
for (int i = 0; i < n; ++i) {
int cur = Integer.parseInt(as[i]);
if (cur != prev) {
ci.add(i);
prev = cur;
}
}
ci.add(n);
init(1, 0, ci.size() - 2);
for (int i = 0; i < q; ++i) {
String[] range = sc.nextLine().split(" ");
int start = Integer.parseInt(range[0]) - 1;
int end = Integer.parseInt(range[1]) - 1;
int ans = solve(start, end);
// System.out.println(ans);
output.append(ans + "\n");
}
n = sc.nextInt();
}
System.out.println(output);
}
static int solve(int start, int end) {
int si = Collections.binarySearch(ci, start);
int ei = Collections.binarySearch(ci, end);
if (si < 0) {
si = -si - 2;
}
if (ei < 0) {
ei = -ei - 2;
}
if (si == ei) {
return end - start + 1;
}
int max = ci.get(si + 1) - start;
max = Math.max(max, end - ci.get(ei) + 1);
if (si + 1 < ei) {
max = Math.max(max, query(1, 0, ci.size() - 2, si + 1, ei - 1));
}
return max;
}
static void init(int node, int s, int e) {
if (s == e) {
max[node] = ci.get(s + 1) - ci.get(s);
return;
}
init(2 * node, s, (s + e) / 2);
init(2 * node + 1, (s + e) / 2 + 1, e);
max[node] = Math.max(max[2 * node], max[2 * node + 1]);
}
static int query(int node, int s, int e, int i, int j) {
if (j < s || e < i) {
return -1;
}
if (i <= s && e <= j) {
return max[node];
}
int v1 = query(node * 2, s, (s + e) / 2, i, j);
int v2 = query(node * 2 + 1, (s + e) / 2 + 1, e, i, j);
return Math.max(v1, v2);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment