Submission #255243

#	Time	Username	Problem	Language	Result	Execution time	Memory
255243		Kastanda	Election (BOI18_election)	C++11	100 / 100	976 ms	43504 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];
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);
        for (int i = 1; i <= q; i ++)
        {
                int l, r;
                scanf("%d%d", &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() - (int)(lower_bound(stk.begin(), stk.end(), X.second) - stk.begin()) + 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;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%s%d", &n, &A[1], &q);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:50:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d", &l, &r);
                 ~~~~~^~~~~~~~~~~~~~~~

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