Submission #1100682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100682		DangKhoizzzz	Election (BOI18_election)	C++14	0 / 100	3 ms	2384 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;

const int INF = 1e9;

struct node
{
    int pre , suf , possuf , pospre , sum;
};

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

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

    if(Lnode.pre == Lnode.sum + Rnode.pre)
    {
        res.pospre = Lnode.pospre;
    }
    else
    {
        if(Lnode.pre < Lnode.sum + Rnode.pre)
        {
            res.pospre = Lnode.pospre;
        }
        else res.pospre = Rnode.pospre;
    }

    if(Rnode.suf == Rnode.sum + Lnode.suf)
    {
        res.possuf = Rnode.possuf;
    }
    else
    {
        if(Rnode.suf < Rnode.sum + Lnode.suf)
        {
            res.possuf = Rnode.possuf;
        }
        else res.possuf = Lnode.possuf;
    }
    return res;
}


node st[maxn*4];
int n , a[maxn];

void build(int id , int l , int r)
{
    if(l == r)
    {
        st[id].pospre = st[id].possuf = l;
        st[id].suf = st[id].pre = min(0 , a[l]);
        st[id].sum = 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(u > v) return {0 , 0 , 0 , 0 , 0};
    if(r < u || l > v) return {INF , INF , -1 , - 1 , 0};

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

    int mid = (l+r)/2;

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

    return merging(Lget , Rget);
}

void query(int l , int r)
{
    node tmp = get(1 , 0 , n , l , r);

    int pospre = tmp.pospre;
    int possuf = tmp.possuf;
    int suf = tmp.suf;
    int pre = tmp.pre;

    //cout << pospre << ' ' << possuf << '\n';

    int cnt1 = -(pre - min(get(1 , 0 , n , l , possuf - 1).pre , 0));
    int cnt2 = -(suf - min(get(1 , 0 , n , pospre + 1 , r).suf , 0));


    cout << -(tmp.pre + tmp.suf) - min(cnt1 , cnt2) << '\n';

}


void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        char ch; cin >> ch;
        a[i] = -1;
        if(ch == 'C') a[i] = 1;
    }

    build(1 , 0 , n);

    int q; cin >> q;

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

}


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

    //freopen("NoSleeping.INP" , "r" , stdin);
    //freopen("NoSleeping.OUT" , "w" , stdout);

    solve();
    return 0;
}

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