Submission #1030093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030093		parsadox2	Election (BOI18_election)	C++17	100 / 100	254 ms	44372 KiB

election

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10;

int n , a[N] , q;

struct SEG{
    struct NODE{
        int mnp , mns , sum , ans;
        NODE()
        {
            mnp = mns = sum = ans = 0;
        }
    };
    NODE t[N << 2];
    NODE Merge(NODE lc , NODE rc)
    {
        NODE res;
        res.mnp = min(lc.mnp , lc.sum + rc.mnp);
        res.mns = min(rc.mns , rc.sum + lc.mns);
        res.sum = lc.sum + rc.sum;
        res.ans = max({-lc.mnp - rc.mns , lc.ans - rc.sum , rc.ans - lc.sum});
        return res;
    }
    void Build(int node = 1 , int nl = 0 , int nr = n)
    {
        if(nr - nl == 1)
        {
            t[node].sum = a[nl];
            t[node].mnp = t[node].mns = min(a[nl] , 0);
            t[node].ans = -t[node].mns;
            return;
        }
        int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
        Build(lc , nl , mid);  Build(rc , mid , nr);
        t[node] = Merge(t[lc] , t[rc]);
        //cout << nl << " " << nr << " " << t[node].ans << endl;
    }
    NODE Get(int l , int r , int node = 1 , int nl = 0 , int nr = n)
    {
        if(nr <= l || r <= nl)
        {
            NODE emp;
            return emp;
        }
        if(l <= nl && nr <= r)
            return t[node];
        int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
        return Merge(Get(l , r , lc , nl , mid) , Get(l , r , rc , mid , nr));
    }
} seg;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    cin >> n;
    for(int i = 0 ; i < n ; i++)
    {
        char c;  cin >> c;
        if(c == 'C')
            a[i] = 1;
        else
            a[i] = -1;
    }
    seg.Build();
    cin >> q;
    for(int i = 0 ; i < q ; i++)
    {
        int l , r;  cin >> l >> r;  l--;
        cout << seg.Get(l , r).ans << '\n';
    }
    return 0;
}

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