Submission #78877

#	Time	Username	Problem	Language	Result	Execution time	Memory
78877		bogdan10bos	Election (BOI18_election)	C++14	100 / 100	821 ms	123956 KiB

election

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef pair<int, int> pii;

pii qry[500005];
int N, Q;
int sol[500005];
char s[500005];
vector<int> stv, queries[500005];

namespace BinaryIndexedTree
{
    int aib[500005];
    void update(int pos, int val)
    {
        for(; pos <= N; pos += (pos & (-pos)))
            aib[pos] += val;
    }

    int query(int pos)
    {
        int ans = 0;
        for(; pos > 0; pos -= (pos & (-pos)))
            ans += aib[pos];
        return ans;
    }

    int query(int st, int dr) { return query(dr) - query(st - 1); }
}

namespace SegmentTree
{
    int sti, dri, pos, val, ans, pfx;
    int sum[2000005], mn[2000005];

    void remake(int nod)
    {
        sum[nod] = sum[nod * 2] + sum[nod * 2 + 1];
        mn[nod] = min(mn[nod * 2], mn[nod * 2 + 1] + sum[nod * 2]);
    }

    void B(int nod, int st, int dr)
    {
        if(st == dr)
        {
            sum[nod] = mn[nod] = s[st];
            return;
        }

        int mij = st + (dr - st) / 2;
        B(nod * 2, st, mij);
        B(nod * 2 + 1, mij + 1, dr);

        remake(nod);
    }

    void U(int nod, int st, int dr)
    {
        if(st == dr)
        {
            sum[nod] = mn[nod] = val;
            return;
        }

        int mij = st + (dr - st) / 2;

        if(pos <= mij)  U(nod * 2, st, mij);
        else    U(nod * 2 + 1, mij + 1, dr);

        remake(nod);
    }

    void Q(int nod, int st, int dr)
    {
        if(sti <= st && dr <= dri)
        {
            ans = min(ans, pfx + mn[nod]);
            pfx += sum[nod];
            return;
        }

        int mij = st + (dr - st) / 2;
        if(sti <= mij)  Q(nod * 2, st, mij);
        if(mij < dri)   Q(nod * 2 + 1, mij + 1, dr);
    }

    void update(int _pos, int _val)
    {
        pos = _pos, val = _val;
        U(1, 1, N);
    }

    int query(int st, int dr)
    {
        sti = st, dri = dr;
        pfx = 0;
        ans = 1 << 30;
        Q(1, 1, N);
        if(ans < 0) return -ans;
        return 0;
    }

    void build() { B(1, 1, N); }
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d\n", &N);
    scanf("%s", s + 1);
    for(int i = 1; i <= N; i++) s[i] = (s[i] == 'C' ? 1 : -1);

    scanf("%d", &Q);
    for(int q = 1; q <= Q; q++)
    {
        int st, dr;
        scanf("%d%d", &st, &dr);
        qry[q] = {st, dr};
        queries[dr].push_back(q);
    }

    SegmentTree::build();
    for(int i = 1; i <= N; i++)
    {
        if(s[i] == -1)
        {
            stv.push_back(i);
            SegmentTree::update(i, 0);
            BinaryIndexedTree::update(i, 1);
        }
        else
        {
            if(!stv.empty())
            {
                int x = stv.back(); stv.pop_back();
                SegmentTree::update(x, -1);
                BinaryIndexedTree::update(x, -1);
            }
        }

        for(auto id: queries[i])
        {
            int st = qry[id].first, dr = qry[id].second;
            sol[id] = SegmentTree::query(st, dr) + BinaryIndexedTree::query(st, dr);
        }
    }

    for(int i = 1; i <= Q; i++)
        printf("%d\n", sol[i]);

    return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n", &N);
     ~~~~~^~~~~~~~~~~~
election.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s + 1);
     ~~~~~^~~~~~~~~~~~~
election.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
election.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &st, &dr);
         ~~~~~^~~~~~~~~~~~~~~~~~

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