Submission #707534

#	Time	Username	Problem	Language	Result	Execution time	Memory
707534		ToroTN	Election (BOI18_election)	C++14	100 / 100	462 ms	27332 KiB

election

#include<bits/stdc++.h>
using namespace std;
int n,t,x,y;
char s[500005];
struct node
{
    int l,r,sum,ans;
} seg[2000005];
node merge(node lft,node rht)
{
    node res;
    res.sum=lft.sum+rht.sum;
    res.l=max(lft.l,lft.sum+rht.l);
    res.r=max(rht.r,rht.sum+lft.r);
    res.ans=max({lft.l+rht.r,lft.ans+rht.sum,rht.ans+lft.sum});
    return res;
}
void build(int tree,int st,int ed)
{
    int md=(st+ed)/2;
    if(st==ed)
    {
        if(s[st]=='T')
        {
            seg[tree].l=seg[tree].r=seg[tree].sum=seg[tree].ans=1;
        }else
        {
            seg[tree].l=seg[tree].r=seg[tree].ans=0;
            seg[tree].sum=-1;
        }
        return;
    }
    build(2*tree,st,md);
    build(2*tree+1,md+1,ed);
    seg[tree]=merge(seg[2*tree],seg[2*tree+1]);
}
node query(int tree,int st,int ed,int l,int r)
{
    int md=(st+ed)/2;
    if(st>r||ed<l)
    {
        return {0,0,0,0};
    }
    if(st>=l&&ed<=r)
    {
        return seg[tree];
    }
    return merge(query(2*tree,st,md,l,r),query(2*tree+1,md+1,ed,l,r));
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n >> s+1;
    cin >> t;
    build(1,1,n);
    while(t--)
    {
        cin >> x >> y;
        printf("%d\n",query(1,1,n,x,y).ans);
    }
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:53:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     cin >> n >> s+1;
      |                 ~^~

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