Submission #346837

#	Time	Username	Problem	Language	Result	Execution time	Memory
346837		JerryLiu06	Election (BOI18_election)	Java	82 / 100	3090 ms	173704 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).ans);
		}
	}
	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); tree[x] = tree[2 * x].add(tree[2 * x + 1]);
	}
	static Node query(int x, int l, int r, int tl, int tr) { int mid = (l + r) / 2;
		if (r < tl || l > tr) return new Node(0, 0, 0, 0); if (tl <= l && r <= tr) { return tree[x]; }
		
		return query(2 * x, l, mid, tl, tr).add(query(2 * x + 1, mid + 1, r, tl, tr));
	}
	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; } 
		
		public Node add(Node n) { Node res = new Node(0, 0, 0, 0);
			res.left = Math.max(left, sum + n.left); res.right = Math.max(right + n.sum, n.right);
			res.sum = sum + n.sum; res.ans = Math.max(Math.max(ans + n.sum, sum + n.ans), left + n.right); return res;
		}
	}
}

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