oj.uz

Submission #346837

# Submission time Handle Problem Language Result Execution time Memory
346837 2021-01-11T07:37:10 Z JerryLiu06 Election (BOI18_election) Java 11
82 / 100
 3000 ms 173704 KB 
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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 107600 KB Output is correct
2 Correct 682 ms 107276 KB Output is correct
3 Correct 667 ms 107136 KB Output is correct
4 Correct 649 ms 107420 KB Output is correct
5 Correct 648 ms 107328 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 107600 KB Output is correct
2 Correct 682 ms 107276 KB Output is correct
3 Correct 667 ms 107136 KB Output is correct
4 Correct 649 ms 107420 KB Output is correct
5 Correct 648 ms 107328 KB Output is correct
6 Correct 1694 ms 140684 KB Output is correct
7 Correct 1665 ms 140872 KB Output is correct
8 Correct 1680 ms 140748 KB Output is correct
9 Correct 1684 ms 140936 KB Output is correct
10 Correct 1663 ms 140648 KB Output is correct
11 Correct 1698 ms 140632 KB Output is correct
12 Correct 1685 ms 140688 KB Output is correct
13 Correct 1696 ms 140848 KB Output is correct
14 Correct 1684 ms 140852 KB Output is correct
15 Correct 1689 ms 140636 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 107600 KB Output is correct
2 Correct 682 ms 107276 KB Output is correct
3 Correct 667 ms 107136 KB Output is correct
4 Correct 649 ms 107420 KB Output is correct
5 Correct 648 ms 107328 KB Output is correct
6 Correct 1694 ms 140684 KB Output is correct
7 Correct 1665 ms 140872 KB Output is correct
8 Correct 1680 ms 140748 KB Output is correct
9 Correct 1684 ms 140936 KB Output is correct
10 Correct 1663 ms 140648 KB Output is correct
11 Correct 1698 ms 140632 KB Output is correct
12 Correct 1685 ms 140688 KB Output is correct
13 Correct 1696 ms 140848 KB Output is correct
14 Correct 1684 ms 140852 KB Output is correct
15 Correct 1689 ms 140636 KB Output is correct
16 Execution timed out 3090 ms 173704 KB Time limit exceeded
17 Halted 0 ms 0 KB -