Submission #1101107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101107		DangKhoizzzz	Election (BOI18_election)	C++14	100 / 100	387 ms	30028 KiB

election

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second

using namespace std;
typedef pair<int,int> pii;

const int maxn = 5e5 + 7;

struct node
{
    int pre , suf , sum , ans;
};

int n , a[maxn];

node st[maxn*4];

node merging(node Lnode , node Rnode)
{
    node res;

    res.sum = Lnode.sum + Rnode.sum;

    res.pre = max(Lnode.pre , Lnode.sum + Rnode.pre);
    res.suf = max(Rnode.suf , Lnode.suf + Rnode.sum);

    int ans1 = Lnode.ans + Rnode.sum;
    int ans2 = Rnode.ans + Lnode.sum;
    int ans3 = Lnode.pre + Rnode.suf;

    res.ans = max(ans1 , max(ans2 , ans3));

    return res;
}

void build(int id , int l , int r)
{
    if(l == r)
    {
        st[id].pre = st[id].suf = max(0 , a[l]);
        st[id].sum = a[l];
        st[id].ans = max(0 , a[l]);
        return;
    }
    int mid = (l+r)/2;

    build(id*2 , l , mid);
    build(id*2+1 , mid+1 , r);

    st[id] = merging(st[id*2] , st[id*2+1]);
}

node get(int id , int l , int r , int u , int v)
{
    if(r < u || l > v) return {0 , 0 , 0 , 0};

    if(u <= l && r <= v) return st[id];

    int mid = (l+r)/2;

    node Lnode = get(id*2 , l , mid , u , v);
    node Rnode = get(id*2+1 , mid+1 , r , u , v);

    return merging(Lnode , Rnode);
}


void solve()
{
    cin >> n ;

    for(int i = 1; i <= n; i++)
    {
        char ch; cin >> ch;

        if(ch == 'T') a[i] = 1;
        else a[i] = -1;
    }

    build(1 , 1, n);

    int q; cin >> q;

    while(q--)
    {
        int l , r;
        cin >> l >> r;

        cout << get(1 , 1, n , l , r).ans << '\n';
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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