Submission #892675

#	Time	Username	Problem	Language	Result	Execution time	Memory
892675		maxFedorchuk	Election (BOI18_election)	C++14	100 / 100	496 ms	44796 KiB

election

#include <bits/stdc++.h>
using namespace std;

struct strk
{
    long long frl;
    long long frr;
    long long riz;
    long long ans;
};

const long long MX=5e5+10;
strk mas[4*MX];

long long n,q;
string s;

strk mrg(strk a,strk b)
{
    strk rt;

    rt.frl=max(a.frl,b.frl+a.riz);
    rt.frr=max(b.frr,a.frr+b.riz);
    rt.riz=a.riz+b.riz;
    rt.ans=max({a.frl+b.frr,a.ans+b.riz,b.ans+a.riz});

    return rt;
}


void build(long long v,long long tl,long long tr)
{
    if(tl==tr)
    {
        if(s[tl]=='C')
        {
            mas[v]={0,0,-1,0};
        }
        else
        {
            mas[v]={1,1,1,1};
        }

        return;
    }

    long long mid=(tl+tr)/2;

    build(v*2,tl,mid);
    build(v*2+1,mid+1,tr);

    mas[v]=mrg(mas[v*2],mas[v*2+1]);

    return;
}

strk zap(long long v,long long tl,long long tr,long long l,long long r)
{
    if(r<tl || tr<l)
    {
        return {0,0,0,0};
    }

    if(l<=tl && tr<=r)
    {
        return mas[v];
    }

    long long mid=(tl+tr)/2;
    return mrg(zap(v*2,tl,mid,l,r),zap(v*2+1,mid+1,tr,l,r));
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n>>s>>q;
    s="*"+s;

    build(1,1,n);

    long long l,r;
    while(q--)
    {
        cin>>l>>r;
        cout<<zap(1,1,n,l,r).ans<<"\n";
    }

    return 0;
}

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