import java.io.*;
import java.util.*;
// Solution Notes: [Balkan Olympiad in Informatics '18] First consider the simpler case when we only need to check from left to right.
// Let a "C" vote count as -1 and a "T" vote count as 1. Then, it is easy to see that the answer to a query on the range [l, r] is simply
// the maximum prefix sum in that range. Similarly, we can apply the same argument when checking from right to left. Now, we need to find
// a way to efficiently combine the two results to obtain the correct answer.
// To do this, we use a segment tree. In each node of the tree, we store the following information: (1) Maximum prefix in the range
// [l, r] (let this be L) (2) Maximum suffix in the range [l, r] (Let this be R) (3) Total sum of the range (Let this be S) (4) Answer
// to the query in range [l, r] (Let this be A). When we combine two nodes u (left child) and v (right child) to make node w, we have that
// w.L = MAX(u.L, u.S + v.L), w.R = MAX(u.R + v.S, v.R), w.S = u.S + v.S.
public class election {
static int MAXN = 500010; static int N, Q; static char[] S = new char[MAXN]; static Node[] tree = new Node[4 * MAXN];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine()); for (int i = 0; i < tree.length; i++) tree[i] = new Node(0, 0, 0, 0);
String in = br.readLine(); for (int i = 1; i <= N; i++) S[i] = in.charAt(i - 1); build(1, 1, N);
Q = Integer.parseInt(br.readLine()); for (int i = 0; i < Q; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
System.out.println(query(1, 1, N, A, B));
}
}
static void build(int x, int l, int r) { int mid = (l + r) / 2;
if (l == r) { if (S[l] == 'C') tree[x] = new Node(0, 0, -1, 0); else tree[x] = new Node(1, 1, 1, 1); return ;}
build(2 * x, l, mid); build(2 * x + 1, mid + 1, r); update(x, l, r);
}
static int query(int x, int l, int r, int tl, int tr) { int mid = (l + r) / 2;
if (r < tl || l > tr) return 0; if (tl <= l && r <= tr) { return tree[x].ans; }
return query(2 * x, l, mid, tl, tr) + query(2 * x + 1, mid + 1, r, tl, tr);
}
static void update(int x, int l, int r) {
tree[x].left = Math.max(tree[2 * x].left, tree[2 * x].sum + tree[2 * x + 1].left);
tree[x].right = Math.max(tree[2 * x].right + tree[2 * x + 1].sum, tree[2 * x + 1].right);
tree[x].sum = tree[2 * x].sum + tree[2 * x + 1].sum;
tree[x].ans = Math.max(Math.max(tree[2 * x].ans + tree[2 * x + 1].sum, tree[2 * x].sum + tree[2 * x + 1].ans), tree[2 * x].left + tree[2 * x + 1].right);
}
static class Node {
public int left, right, sum, ans;
public Node(int a, int b, int c, int d) { left = a; right = b; sum = c; ans = d; }
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
504 ms |
84716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
504 ms |
84716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
504 ms |
84716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
