Submission #869246

#	Time	Username	Problem	Language	Result	Execution time	Memory
869246		sofija6	Election (BOI18_election)	C++14	100 / 100	511 ms	48304 KiB

election

#include <bits/stdc++.h>
#define ll long long
#define MAXN 500010
using namespace std;
ll n,a[MAXN],sz;
struct element
{
    ll pref=0,suff=0,sum=0,minn;
};
element Merge(element x,element y)
{
    element z;
    z.pref=min(x.pref,x.sum+y.pref);
    z.suff=min(y.suff,x.suff+y.sum);
    z.sum=x.sum+y.sum;
    z.minn=min({0ll,x.pref+y.suff,x.minn+y.sum,x.sum+y.minn});
    return z;
}
element neutral_element;
struct seg_tree
{
    vector<element> st;
    void Init()
    {
        sz=1;
        while (sz<n)
            sz <<= 1;
        st.resize(2*sz+2);
    }
    void Build()
    {
        for (ll i=sz;i<sz+n;i++)
            st[i]={min(0ll,a[i-sz+1]),min(0ll,a[i-sz+1]),a[i-sz+1],min(0ll,a[i-sz+1])};
        for (ll i=sz-1;i>0;i--)
            st[i]=Merge(st[2*i],st[2*i+1]);
    }
    element Calc(ll l,ll r,ll x,ll lx,ll rx)
    {
        if (lx>r || rx<l)
            return neutral_element;
        if (lx>=l && rx<=r)
            return st[x];
        ll mid=(lx+rx)/2;
        return Merge(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
    }
};
seg_tree S;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll q,l,r;
    string s;
    cin >> n >> s;
    for (ll i=0;i<n;i++)
        a[i+1]=(s[i]=='T')?-1 : 1;
    S.Init();
    S.Build();
    cin >> q;
    while (q--)
    {
        cin >> l >> r;
        element ans=S.Calc(l,r,1,1,sz);
        cout << abs(ans.minn) << "\n";
    }
    return 0;
}

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