Submission #254610

#	Time	Username	Problem	Language	Result	Execution time	Memory
254610		Kastanda	Election (BOI18_election)	C++14	0 / 100	11 ms	12160 KiB

election

// M
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 500005, MXS = N * 4;
int n, q, R[N];
//char A[N];
string A;
int LZ[MXS], MN[MXS];
vector < pair < int , int > > V[N];
inline void Shift(int id)
{
        LZ[lc] += LZ[id];
        MN[lc] += LZ[id];
        LZ[rc] += LZ[id];
        MN[rc] += LZ[id];
        LZ[id] = 0;
}
void Add(int le, int ri, int val, int id = 1, int l = 0, int r = n + 1)
{
        if (ri <= l || r <= le)
                return ;
        if (le <= l && r <= ri)
        {
                LZ[id] += val;
                MN[id] += val;
                return ;
        }
        Shift(id);
        Add(le, ri, val, lc, l, md);;
        Add(le, ri, val, rc, md, r);
        MN[id] = min(MN[lc], MN[rc]);
}
int GetMin(int le, int ri, int id = 1, int l = 0, int r = n + 1)
{
        if (ri <= l || r <= le)
                return MXS;
        if (le <= l && r <= ri)
                return MN[id];
        Shift(id);
        return min(GetMin(le, ri, lc, l, md), GetMin(le, ri, rc, md, r));
}
int main()
{
        //scanf("%d%s%d", &n, &A[1], &q);
        cin >> n >> A >> q;
        A = "#" + A;
        for (int i = 1; i <= q; i ++)
        {
                int l, r;
                //scanf("%d%d", &l, &r);
                cin >> l >> r;
                V[r].push_back({i, l});
        }
        vector < int > stk;
        for (int i = 1; i <= n; i ++)
        {
                if (A[i] == 'C')
                {
                        if (stk.size())
                                Add(stk.back(), n + 1, -1), stk.pop_back();
                        Add(i, n + 1, 1);
                }
                else
                        stk.push_back(i);
                for (auto X : V[i])
                        R[X.first] = (int)stk.size() + max(-(GetMin(X.second, i + 1) - GetMin(X.second - 1, X.second)), 0);
        }
        for (int i = 1; i <= q; i ++)
                printf("%d\n", R[i]);
        return 0;
}

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