Submission #942791

#	Time	Username	Problem	Language	Result	Execution time	Memory
942791		12345678	Election (BOI18_election)	C++17	100 / 100	422 ms	41320 KiB

election

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

int n, vl[nx], q, l, r;
string str;

struct segtree
{
    struct node
    {
        int l, r, sm, ans;
        node(): l(0), r(0), sm(0), ans(-1e9){}
        node(int x): l(max(0, x)), r(max(0, x)), sm(x), ans(max(0, x)){}
        friend node operator+(const node &a, const node &b)
        {
            if (a.ans==-1e9) return b;
            if (b.ans==-1e9) return a;
            node res;
            res.l=max(a.l, a.sm+b.l);
            res.r=max(a.r+b.sm, b.r);
            res.sm=a.sm+b.sm;
            res.ans=max({a.ans+b.sm, a.sm+b.ans, a.l+b.r});
            return res;
        }
    } d[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]=node(vl[l]), void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=d[2*i]+d[2*i+1];
        //cout<<l<<' '<<r<<' '<<d[i].l<<' '<<d[i].r<<' '<<d[i].sm<<' '<<d[i].ans<<'\n';
    }
    node query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return node();
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>str;
    str=' '+str;
    for (int i=1; i<=n; i++) vl[i]=(str[i]=='T')?1:-1;
    s.build(1, n, 1);
    cin>>q;
    while (q--) cin>>l>>r, cout<<s.query(1, n, 1, l, r).ans<<'\n';
}

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