Submission #366904

#	Time	Username	Problem	Language	Result	Execution time	Memory
366904		HenryH	Election (BOI18_election)	Java	100 / 100	1750 ms	89452 KiB

election

import java.util.*;
import java.io.*;

public class election {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer t = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(t.nextToken());
		String votes = "";
		votes = br.readLine();
		segTree = new Segment[4 * n];
		build(0, 0, n-1, votes);
		t = new StringTokenizer(br.readLine());
		int q = Integer.parseInt(t.nextToken());
		for(int i = 0; i < q; i++) {
			t = new StringTokenizer(br.readLine());
			int curr1 = Integer.parseInt(t.nextToken()) - 1;
			int curr2 = Integer.parseInt(t.nextToken()) - 1;
			pw.println(query(0, curr1, curr2, 0, n-1, segTree).answer);
		}
		pw.close();
	}
	public static Segment[] segTree;
	public static Segment query(int node, int start, int end, int j, int k, Segment[] segTree) {
		if (k < j)return new Segment(0, 0, 0, 0);
		if (k < start || j > end) {
			return new Segment(0, 0, 0, 0);
		}
		if (start <= j && k <= end) {
			return segTree[node];
		}
		int midPt = (j + k)/2;
		return merge(query(node * 2 + 1, start, end, j, midPt, segTree), query(node * 2 + 2, start, end, midPt + 1, k, segTree));
	}
	public static void build(int node, int l, int r, String s) {
	    if (l == r) {
	        if (s.charAt(l) == 'T') segTree[node] = new Segment(1, 1, 1, 1);
	        else segTree[node] = new Segment(0, 0, -1, 0);
	    } else {
	        int mid = (l + r) / 2;
	        build(node * 2+1, l, mid, s);
	        build(node * 2 + 2, mid + 1, r, s);
	        segTree[node] = merge(segTree[node * 2+1], segTree[node * 2 + 2]);
	    }
	}
	public static Segment merge(Segment seg1, Segment seg2) {
		int newL = Math.max(seg1.maxL, seg1.total + seg2.maxL);
		int newR = Math.max(seg2.maxR, seg2.total + seg1.maxR);
		int total = seg1.total + seg2.total;
		int newAns = Math.max(Math.max(seg1.answer + seg2.total, seg1.total + seg2.answer), seg1.maxL + seg2.maxR);
		return new Segment(newL, newR, total, newAns);
	}
}

class Segment{
	int maxL;
	int maxR;
	int total;
	int answer;
	public Segment(int a, int b, int c, int d) {
		maxL = a;
		maxR = b;
		total = c;
		answer = d;
	}
	public String toString() {
		return maxL + " " + maxR + " " + total + " " + answer;
	}
}

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