Submission #855801

#	Time	Username	Problem	Language	Result	Execution time	Memory
855801		ivaziva	Election (BOI18_election)	C++14	100 / 100	1206 ms	44376 KiB

election

#include <bits/stdc++.h>

using namespace std;

#define MAXN 500010

long long n;
long long q;
string s;
pair<pair<long long,long long>,pair<long long,long long>> seg[MAXN*4];

void build(long long node,long long l,long long r)
{
    if (l==r)
    {
        if (s[l-1]=='T') seg[node]={{1,1},{1,1}};
        else seg[node]={{0,0},{-1,0}};
    }
    else
    {
        long long mid=(l+r)/2;
        build(2*node,l,mid);
        build(2*node+1,mid+1,r);
        seg[node].first.first=max(seg[2*node].first.first,seg[2*node].second.first+seg[2*node+1].first.first);
        seg[node].first.second=max(seg[2*node].first.second+seg[2*node+1].second.first,seg[2*node+1].first.second);
        seg[node].second.first=seg[2*node].second.first+seg[2*node+1].second.first;
        seg[node].second.second=max(max(seg[2*node].second.second+seg[2*node+1].second.first,seg[2*node].second.first+seg[2*node+1].second.second),seg[2*node].first.first+seg[2*node+1].first.second);
    }
}

pair<pair<long long,long long>,pair<long long,long long>> sol(long long node,long long l,long long r,long long a,long long b)
{
    if (a>b) return {{0,0},{0,0}};
    if (l==a and r==b) return seg[node];
    long long mid=(l+r)/2;
    pair<pair<long long,long long>,pair<long long,long long>> val1=sol(2*node,l,mid,a,min(b,mid));
    pair<pair<long long,long long>,pair<long long,long long>> val2=sol(2*node+1,mid+1,r,max(a,mid+1),b);
    pair<pair<long long,long long>,pair<long long,long long>> val;
    val.first.first=max(val1.first.first,val1.second.first+val2.first.first);
    val.first.second=max(val1.first.second+val2.second.first,val2.first.second);
    val.second.first=val1.second.first+val2.second.first;
    val.second.second=max(max(val1.second.second+val2.second.first,val1.second.first+val2.second.second),val1.first.first+val2.first.second);
    return val;
}

int main()
{
    cin>>n>>s;
    build(1,1,n);
    cin>>q;
    for (long long i=1;i<=q;i++)
    {
        long long l,r;
        cin>>l>>r;
        cout<<sol(1,1,n,l,r).second.second<<endl;
    }
}

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