Submission #346123

#	Time	Username	Problem	Language	Result	Execution time	Memory
346123		JerryLiu06	Election (BOI18_election)	Java	0 / 100	504 ms	84716 KiB

election

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

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18