Submission #261509

#	Time	Username	Problem	Language	Result	Execution time	Memory
261509		Kastanda	Street Lamps (APIO19_street_lamps)	C++11	100 / 100	3419 ms	233164 KiB

street_lamps

// M
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 300005, MXS = N * 4, MXF = N * 19;
int n, q, ts, TP[N], qa[N], qb[N], St[MXS], F[MXF];
char A[N];
set < int > ST;
map < pair < int , int > , int > MP;
vector < int > V[N], VS[MXS], fcl[MXS], fcr[MXS];
inline void AddFen(int i, int val)
{
        for (i ++; i < MXF; i += i & - i)
                F[i] += val;
}
inline int GetFen(int i)
{
        int rt = 0;
        for (i ++; i; i -= i & - i)
                rt += F[i];
        return rt;
}
inline void AddFen(int l, int r, int val)
{
        AddFen(l, val);
        AddFen(r, -val);
}
void Build(int id = 1, int l = 1, int r = n + 2)
{
        if (r - l < 2)
        {
                VS[id] = V[l];
                St[id] = ts;
                ts += (int)VS[id].size();
                return ;
        }
        Build(lc, l, md);
        Build(rc, md, r);
        merge(VS[lc].begin(), VS[lc].end(), VS[rc].begin(), VS[rc].end(), back_inserter(VS[id]));
        VS[id].resize(unique(VS[id].begin(), VS[id].end()) - VS[id].begin());
        int le = 0, ri = 0;
        for (int a : VS[id])
        {
                while (le < (int)VS[lc].size() && VS[lc][le] < a)
                        le ++;
                while (ri < (int)VS[rc].size() && VS[rc][ri] < a)
                        ri ++;
                fcl[id].push_back(le);
                fcr[id].push_back(ri);
        }
        fcl[id].push_back((int)VS[lc].size());
        fcr[id].push_back((int)VS[rc].size());
        St[id] = ts;
        ts += (int)VS[id].size();
}
void AddSeg(int le, int ri, int val, int lq, int rq, int id = 1, int l = 1, int r = n + 2)
{
        if (ri <= l || r <= le || rq <= lq)
                return ;
        if (le <= l && r <= ri)
                return void(AddFen(St[id] + lq, St[id] + rq, val));
        AddSeg(le, ri, val, fcl[id][lq], fcl[id][rq], lc, l, md);
        AddSeg(le, ri, val, fcr[id][lq], fcr[id][rq], rc, md, r);
}
int GetSeg(int i, int b, int id = 1, int l = 1, int r = n + 2)
{
        int rt = GetFen(St[id] + b);
        if (r - l < 2)
                return rt;
        if (i < md)
                return GetSeg(i, fcl[id][b], lc, l, md) + rt;
        return GetSeg(i, fcr[id][b], rc, md, r) + rt;
}
inline void Add(int l, int r, int val)
{
        r ++; // Changing segments to points
        if (!val) return ;
        int lq = lower_bound(VS[1].begin(), VS[1].end(), l) - VS[1].begin();
        int rq = lower_bound(VS[1].begin(), VS[1].end(), r) - VS[1].begin();
        AddSeg(l, r, val, lq, rq);
}
inline int Get(int a, int b)
{
        b = lower_bound(VS[1].begin(), VS[1].end(), b) - VS[1].begin();
        return GetSeg(a, b);
}
inline void TurnOff(int i, int tnw)
{
        assert(A[i]); A[i] = 0;
        auto it = ST.lower_bound(i);
        int ri = * it; it --;
        int le = * it;
        le ++; ri --;
        ST.insert(i);

        Add(le, ri + 1, tnw - MP[{le, ri}]);
        MP[{le, ri}] = -1;

        if (le < i)
                MP[{le, i - 1}] = tnw;
        if (i < ri)
                MP[{i + 1, ri}] = tnw;
}
inline void TurnOn(int i, int tnw)
{
        assert(!A[i]); A[i] = 1;
        ST.erase(i);
        auto it = ST.lower_bound(i);
        int ri = * it; it --;
        int le = * it;
        le ++; ri --;

        if (le < i)
                Add(le, i, tnw - MP[{le, i - 1}]);
        if (i < ri)
                Add(i + 1, ri + 1, tnw - MP[{i + 1, ri}]);

        MP[{le, ri}] = tnw;
}
int main()
{
        scanf("%d%d%s", &n, &q, &A[1]);
        for (int i = 1; i <= q; i ++)
        {
                char ss[10];
                scanf("%s%d", ss, &qa[i]);
                if (ss[0] == 'q')
                        scanf("%d", &qb[i]), TP[i] = 1, V[qa[i]].push_back(qb[i]);
                else
                        TP[i] = 2;
        }
        for (int i = 1; i <= n + 1; i ++)
                sort(V[i].begin(), V[i].end());
        Build();
        for (int i = 1; i <= n; i ++)
                A[i] -= '0';
        ST.insert(0);
        ST.insert(n + 1);
        for (int i = 1; i <= n; i ++)
                if (!A[i])
                        ST.insert(i);
        for (int i = 1; i <= n; i ++)
                if (A[i] && !A[i - 1])
                {
                        int r = i;
                        while (r <= n && A[r])
                                r ++;
                        MP[{i, r - 1}] = 0;
                }
        for (int i = 1; i <= q; i ++)
        {
                if (TP[i] == 2)
                {
                        if (A[qa[i]])
                                TurnOff(qa[i], i);
                        else
                                TurnOn(qa[i], i);
                        continue;
                }
                int a = qa[i], b = qb[i];
                if (A[a])
                        TurnOff(a, i), TurnOn(a, i);
                printf("%d\n", Get(a, b));
        }
        return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%s", &n, &q, &A[1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:128:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%s%d", ss, &qa[i]);
                 ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:130:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                         scanf("%d", &qb[i]), TP[i] = 1, V[qa[i]].push_back(qb[i]);
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20