Submission #760508

#	Time	Username	Problem	Language	Result	Execution time	Memory
760508		vjudge1	Election (BOI18_election)	C++17	100 / 100	1055 ms	20388 KiB

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 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18