oj.uz

Submission #366904

# Submission time Handle Problem Language Result Execution time Memory
366904 2021-02-15T16:46:02 Z HenryH Election (BOI18_election) Java 11
100 / 100
 1750 ms 89452 KB 
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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 14252 KB Output is correct
2 Correct 239 ms 14064 KB Output is correct
3 Correct 236 ms 14036 KB Output is correct
4 Correct 234 ms 13936 KB Output is correct
5 Correct 246 ms 14064 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 14252 KB Output is correct
2 Correct 239 ms 14064 KB Output is correct
3 Correct 236 ms 14036 KB Output is correct
4 Correct 234 ms 13936 KB Output is correct
5 Correct 246 ms 14064 KB Output is correct
6 Correct 668 ms 23240 KB Output is correct
7 Correct 642 ms 23244 KB Output is correct
8 Correct 692 ms 23132 KB Output is correct
9 Correct 691 ms 23272 KB Output is correct
10 Correct 690 ms 23164 KB Output is correct
11 Correct 709 ms 23268 KB Output is correct
12 Correct 665 ms 23452 KB Output is correct
13 Correct 665 ms 23500 KB Output is correct
14 Correct 689 ms 23188 KB Output is correct
15 Correct 680 ms 23172 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 14252 KB Output is correct
2 Correct 239 ms 14064 KB Output is correct
3 Correct 236 ms 14036 KB Output is correct
4 Correct 234 ms 13936 KB Output is correct
5 Correct 246 ms 14064 KB Output is correct
6 Correct 668 ms 23240 KB Output is correct
7 Correct 642 ms 23244 KB Output is correct
8 Correct 692 ms 23132 KB Output is correct
9 Correct 691 ms 23272 KB Output is correct
10 Correct 690 ms 23164 KB Output is correct
11 Correct 709 ms 23268 KB Output is correct
12 Correct 665 ms 23452 KB Output is correct
13 Correct 665 ms 23500 KB Output is correct
14 Correct 689 ms 23188 KB Output is correct
15 Correct 680 ms 23172 KB Output is correct
16 Correct 1739 ms 88320 KB Output is correct
17 Correct 1527 ms 88132 KB Output is correct
18 Correct 1627 ms 88144 KB Output is correct
19 Correct 1468 ms 87780 KB Output is correct
20 Correct 1716 ms 87412 KB Output is correct
21 Correct 1716 ms 89172 KB Output is correct
22 Correct 1728 ms 88964 KB Output is correct
23 Correct 1747 ms 89452 KB Output is correct
24 Correct 1745 ms 89188 KB Output is correct
25 Correct 1750 ms 88504 KB Output is correct