Submission #760508

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
760508	2023-06-17T16:44:54 Z	vjudge1	Election (BOI18_election)	C++17	100 / 100	1055 ms	20388 KB

election

#include <bits/stdc++.h>

using namespace std;

class Node {
    public:
	int l_max, r_max, t, ans;

};
	Node f(Node a, Node b) {
		Node r;
		r.l_max=max(a.l_max, b.l_max + a.t);
		r.r_max=max(a.r_max + b.t, b.r_max);
		r.t=a.t+b.t;
		r.ans=max(max(a.ans + b.t, b.ans + a.t), a.l_max + b.r_max);
		return r;
	}
Node v[2000001];
int n;
string s;


void build(int node=1, int l=1, int r=n) {
	if (l==r) {
		if (s[l]=='T') v[node]={1, 1, 1, 1};
		else v[node]={0, 0, -1, 0};
	} else {
		int mid=(l + r)/2;
		build(node*2, l, mid);
		build(node*2+1, mid + 1, r);
		v[node]=f(v[node*2],v[node*2+1]);
	}
}


Node query(int a, int b, int node = 1, int l = 1, int r = n) {
	if (l>b||r<a) return {0, 0, 0, 0};
	if (l>=a&&r<=b) return v[node];
	int mid=(l+r)/2;
	return f(query(a, b, node*2, l, mid),query(a, b, node*2+1, mid+1, r));

}


int main() {
	cin>>n>>s;
	s=' '+s;
	build();
	int q;
	cin>>q;
	while (q--) {
		int a, b;
		cin>>a>>b;
		cout<<query(a, b).ans<<'\n';
	}
}

Subtask #1

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	340 KB	Output is correct
2	Correct	4 ms	340 KB	Output is correct
3	Correct	4 ms	340 KB	Output is correct
4	Correct	4 ms	340 KB	Output is correct
5	Correct	4 ms	340 KB	Output is correct

Subtask #2

54.0 / 54.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	340 KB	Output is correct
2	Correct	4 ms	340 KB	Output is correct
3	Correct	4 ms	340 KB	Output is correct
4	Correct	4 ms	340 KB	Output is correct
5	Correct	4 ms	340 KB	Output is correct
6	Correct	133 ms	4820 KB	Output is correct
7	Correct	134 ms	4840 KB	Output is correct
8	Correct	127 ms	4772 KB	Output is correct
9	Correct	123 ms	4760 KB	Output is correct
10	Correct	128 ms	4700 KB	Output is correct
11	Correct	129 ms	4808 KB	Output is correct
12	Correct	129 ms	4888 KB	Output is correct
13	Correct	131 ms	4888 KB	Output is correct
14	Correct	130 ms	4768 KB	Output is correct
15	Correct	129 ms	4824 KB	Output is correct

Subtask #3

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	340 KB	Output is correct
2	Correct	4 ms	340 KB	Output is correct
3	Correct	4 ms	340 KB	Output is correct
4	Correct	4 ms	340 KB	Output is correct
5	Correct	4 ms	340 KB	Output is correct
6	Correct	133 ms	4820 KB	Output is correct
7	Correct	134 ms	4840 KB	Output is correct
8	Correct	127 ms	4772 KB	Output is correct
9	Correct	123 ms	4760 KB	Output is correct
10	Correct	128 ms	4700 KB	Output is correct
11	Correct	129 ms	4808 KB	Output is correct
12	Correct	129 ms	4888 KB	Output is correct
13	Correct	131 ms	4888 KB	Output is correct
14	Correct	130 ms	4768 KB	Output is correct
15	Correct	129 ms	4824 KB	Output is correct
16	Correct	1039 ms	19228 KB	Output is correct
17	Correct	969 ms	19324 KB	Output is correct
18	Correct	1004 ms	19312 KB	Output is correct
19	Correct	969 ms	18820 KB	Output is correct
20	Correct	1038 ms	18288 KB	Output is correct
21	Correct	1030 ms	20128 KB	Output is correct
22	Correct	1036 ms	19988 KB	Output is correct
23	Correct	1026 ms	20388 KB	Output is correct
24	Correct	1041 ms	19848 KB	Output is correct
25	Correct	1055 ms	19436 KB	Output is correct