Submission #776431

#	Time	Username	Problem	Language	Result	Execution time	Memory
776431		Dzadzo	Election (BOI18_election)	C++14	100 / 100	584 ms	47728 KiB

election

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vector<int>>
#define INF LLONG_MAX
#define MOD 1000000007
#define MAXN 500000
using namespace std;
struct node{
	int L,R,S,A;
};
node t[4*MAXN+1];
node merge(node a,node b){
	node res;
	res.L=max(a.L,a.S+b.L);
	res.R=max(b.R,b.S+a.R);
	res.S=a.S+b.S;
	res.A=max({a.A+b.S,a.S+b.A,a.L+b.R});
	return res;
}
void build(int a[],int v,int tl,int tr){
	if (tl==tr){
		if (a[tl]==1)t[v]={1,1,1,1}; else t[v]={0,0,-1,0};
	}else{
		int tm=(tl+tr)/2;
		build(a,v*2,tl,tm);
		build(a,v*2+1,tm+1,tr);
		t[v]=merge(t[v*2],t[v*2+1]);
	}
}
node query(int v,int tl,int tr,int l,int r){
	if (l>r)return {0,0,0,0};
	if (tl==l && tr==r)return t[v];
	int tm=(tl+tr)/2;
	return merge(query(v*2,tl,tm,l,min(r,tm)),query(v*2+1,tm+1,tr,max(l,tm+1),r));
}
int32_t main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n;
	cin>>n;
	int a[n+1];
	for (int i=1;i<=n;i++){
		char c;
		cin>>c;
		if (c=='T')a[i]=1; else a[i]=-1;
	}
	build(a,1,1,n);
	int q;
	cin>>q;
	while (q--){
		int l,r;
		cin>>l>>r;
		cout<<query(1,1,n,l,r).A<<"\n";
	}	
}

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