Submission #942749

#	Time	Username	Problem	Language	Result	Execution time	Memory
942749		irmuun	Election (BOI18_election)	C++17	100 / 100	423 ms	74772 KiB

election

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct Info{
    ll pre=0,suf=0,sum=0,ans=0;
    Info(){*this=Info(0);}
    Info(ll x){
        pre=suf=ans=max(0ll,x);
        sum=x;
    }
};

Info operator+(Info l,Info r){
    Info res;
    res.pre=max(l.pre,l.sum+r.pre);
    res.suf=max(r.sum+l.suf,r.suf);
    res.sum=l.sum+r.sum;
    res.ans=max({l.ans+r.sum,l.sum+r.ans,l.pre+r.suf});
    return res;
}

struct segtree{
    ll n;
    string s;
    vector<Info>d;
    segtree(string str){
        s=str;
        n=s.size();
        d.resize(4*n);
        build(1,0,n-1);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            ll x=(s[l]=='T'?1:-1);
            d[node].pre=d[node].suf=d[node].ans=max(0ll,x);
            d[node].sum=x;
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=d[node*2]+d[node*2+1];
    }
    Info query(ll node,ll l,ll r,ll L,ll R){
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        if(R<=mid){
            return query(node*2,l,mid,L,R);
        }
        if(mid+1<=L){
            return query(node*2+1,mid+1,r,L,R);
        }
        return query(node*2,l,mid,L,R)+query(node*2+1,mid+1,r,L,R);
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n;
    cin>>n;
    string s;
    cin>>s;
    segtree sg(s);
    ll q;
    cin>>q;
    while(q--){
        ll l,r;
        cin>>l>>r;
        l--,r--;
        cout<<sg.query(1,0,n-1,l,r).ans<<"\n";
    }
}

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