Submission #361373

#	Time	Username	Problem	Language	Result	Execution time	Memory
361373		ngpin04	Election (BOI18_election)	C++14	0 / 100	26 ms	39532 KiB

election

#include <bits/stdc++.h>

using namespace std;

struct segnode
{
    int l,r,sum,val;
    bool p;

    segnode(int _l = 0, int _r = 0, int _sum = 0, int _val = 0, bool _p = 0)
    {
        l = _l;
        r = _r;
        sum = _sum;
        val = _val;
        p = _p;
    }

    segnode operator + (const segnode &s)
    {
        segnode res;

        res.p = p | s.p;
        res.l = l;
        res.r = s.r;

        if (!p)
            res.l += s.l;

        if (!s.p)
            res.r += r;

        int mid = r + s.l;

        int sub = min({mid, sum, s.sum});
        res.sum = sum + s.sum - sub;
        res.val = val + s.val - sub;
        return res;
    }
};

const int N = 5e5 + 5;

segnode st[4 * N];

int a[N];
int n;

void build(int id, int l, int r)
{
    if (l == r)
    {
        if (a[l] == 0)
            st[id] = segnode(1, 1, 0, 1, 0);
        else
            st[id] = segnode(0, 0, 1, 0, 1);
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    st[id] = st[id << 1] + st[id << 1 | 1];
}

segnode getval(int id, int l, int r, int u, int v)
{
    if (l > v || r < u)
        return segnode();
    if (l >= u && r <= v)
        return st[id];
    int mid = (l + r) >> 1;
    segnode lnode = getval(id << 1, l, mid, u, v);
    segnode rnode = getval(id << 1 | 1, mid + 1, r, u, v);
    return lnode + rnode;
}

int getans(int l, int r)
{
    return getval(1, 1, n, l, r).val;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("elections.in","r",stdin);
    //freopen("elections.out","w",stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        char c;
        cin >> c;
        a[i] = (c == 'C');
    }

    build(1, 1, n);

    int q;
    cin >> q;
    while (q--)
    {
        int l,r;
        cin >> l >> r;
        cout << getans(l, r) << "\n";
    }

    return 0;
}

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