Submission #599814

#	Time	Username	Problem	Language	Result	Execution time	Memory
599814		Ozy	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	282 ms	24312 KiB

street_lamps

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)

#define MAX 300000
#define ini first.first
#define t first.second
#define f second

#define fin second.first
#define tiempo second.second

lli n,q,last,a,b,dif;
string st,com;
set<pair< pair<lli,lli> ,lli> > rangos;
set<pair< pair<lli,lli> ,lli> >::iterator l,r;
pair< pair<lli,lli> ,lli> ran,x;
lli bit[MAX+2],res[MAX+2];
//inicio, tipo, final tiempo
vector< pair< pair<lli,lli>, pair<lli,lli> > > orden;

void update(lli pos, lli val) {
    while (pos <= n) {
        bit[pos] += val;
        pos += pos&(-pos);
    }
    return;
}

lli acumula(lli pos) {
    lli res = 0;
    while (pos > 0) {
        res += bit[pos];
        pos -= pos&(-pos);
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    cin >> st;
    st = '0' + st + '0';

    //inicializar en base al string
    last = -1;
    rep(i,1,n+1) {
        if (st[i] == '0') {
            if (last != -1) rangos.insert({{last,0},i-1});
            last = -1;
        }
        else if (last == -1) last = i;
    }

    //todos los toggle events suceden primero
    rep(Q,1,q) {
        cin >> com >> a;
        if (com[0] == 't') {
            res[Q] = -1;

            if (st[a] == '0') {
                //creo, uno o agrando
                if (st[a+1] == '1') {
                    if (st[a-1] == '1') {
                        //unir ambos ragos
                        l = rangos.upper_bound({{a+1,0},0});
                        r = l;
                        l--;

                        x.f = (*r).f;
                        x.ini = (*l).ini;
                        x.t = Q;

                        ran = (*l);
                        dif = Q - ran.t;
                        orden.push_back({{ran.ini,-1},{ran.f,dif}});

                        ran = (*r);
                        dif = Q - ran.t;
                        orden.push_back({{ran.ini,-1},{ran.f,dif}});

                        rangos.erase(l);
                        rangos.erase(r);
                        rangos.insert(x);
                    }
                    else {
                        //solo derecha
                        r = rangos.upper_bound({{a+1,0},0});

                        x.f = (*r).f;
                        x.ini = a;
                        x.t = Q;

                        ran = (*r);
                        dif = Q - ran.t;
                        orden.push_back({{ran.ini,-1},{ran.f,dif}});

                        rangos.erase(r);
                        rangos.insert(x);
                    }
                }
                else if (st[a-1] == '1') {
                    //solo izqueireda
                    l = rangos.upper_bound({{a+1,0},0});
                    l--;
                    x.f = a;
                    x.ini = (*l).ini;
                    x.t = Q;

                    ran = (*l);
                    dif = Q - ran.t;
                    orden.push_back({{ran.ini,-1},{ran.f,dif}});

                    rangos.erase(l);
                    rangos.insert(x);
                }
                else rangos.insert( {{a,Q},a });

                st[a] = '1';
            }
            else {
                // parte rango
                r = rangos.upper_bound({{a+1,0},0});
                r--;

                ran = (*r);
                rangos.erase(r);

                dif = Q - ran.t;
                orden.push_back({{ran.ini,-1},{ran.f,dif}});

                if (st[a-1] == '1') rangos.insert({ {ran.ini,Q}, a-1});
                if (st[a+1] == '1') rangos.insert({ {a+1, Q}, ran.f});

                st[a] = '0';
            }

        }
        else {
            cin >> b;
            b--;
            //agrego los eventos y al final proceso
            orden.push_back({ {a,Q},{b,Q}});

            r = rangos.upper_bound({{a+1,0},0});
            if (r != rangos.begin()) {
                r--;
                if ((*r).f >= b) res[Q] = Q - (*r).t;
            }
        }
    }
    sort(orden.begin(), orden.end());

    for(auto act : orden) {
        //debugsl(act.ini);
        //debugsl(act.fin);
        //debugsl(act.t);
        //debug(act.tiempo);

        if (act.t == -1) update(act.fin,act.tiempo);
        else {
            a = acumula(n);
            b = acumula(act.fin-1);

            //debugsl(a);
            //debug(b);

            res[act.t] += a-b;
        }
    }

    rep(i,1,q) if (res[i] > -1) cout << res[i] << "\n";
}

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