Submission #1073684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073684		andrei_iorgulescu	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1780 ms	101280 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

int n, q;
char a[300005], a_ret[300005];

vector<int> ps[300005], aib[300005];
vector<pair<int,int>> vv;

struct event
{
    int tip, x, y;///doar x daca e tip 1 (upd), altfel tip 2 (query)
};

event v[300005];

void build_aib2d_stuff()
{
    sort(vv.begin(), vv.end(), [](pair<int,int> A, pair<int,int> B)
    {
        return A.second < B.second;
    });
    for (int i = 1; i <= n; i++)
        ps[i].push_back(0);
    for (auto it : vv)
    {
        for (int i = it.first; i <= n; i += (i & -i))
            if (ps[i].back() != it.second)
                ps[i].push_back(it.second);
        for (int i = it.first; i > 0; i -= (i & -i))
            if (ps[i].back() != it.second)
                ps[i].push_back(it.second);
    }
    for (int i = 1; i <= n; i++)
        aib[i].resize(ps[i].size());
}

int get_pos(int unde, int y)
{
    int st = 0, pas = 1 << 19;
    while (pas != 0)
    {
        if (st + pas < ps[unde].size() and ps[unde][st + pas] <= y)
            st += pas;
        pas /= 2;
    }
    if (ps[unde][st] != y)
        assert(false);
    return st;
}

void update(int x, int y, int val)
{
    for (int i = x; i <= n; i += (i & -i))
    {
        for (int j = get_pos(i,y); j < ps[i].size(); j += (j & -j))
            aib[i][j] += val;
    }
}

int query(int x, int y)
{
    int rr = 0;
    for (int i = x; i > 0; i -= (i & -i))
    {
        for (int j = get_pos(i, y); j > 0; j -= (j & -j))
            rr += aib[i][j];
    }
    return rr;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i], a_ret[i] = a[i];
    for (int i = 1; i <= q; i++)
    {
        string type;
        cin >> type;
        if (type == "toggle")
        {
            v[i].tip = 1;
            cin >> v[i].x;
        }
        else
        {
            v[i].tip = 2;
            cin >> v[i].x >> v[i].y, v[i].y--;
        }
    }
    for (int i = 1; i <= q; i++)
    {
        if (v[i].tip == 2)
        {
            vv.push_back({v[i].x, n});
            vv.push_back({v[i].x, v[i].y - 1});
        }
    }
    set<pair<int,int>> scvmax;
    map<pair<int,int>, int> beg;
    int s = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == '0')
        {
            if (s != 0)
            {
                scvmax.insert({s, i - 1});
                s = 0;
            }
            s = 0;
        }
        else
        {
            if (s == 0)
                s = i;
        }
    }
    if (s != 0)
        scvmax.insert({s, n});
    for (int i = 1; i <= q; i++)
    {
        if (v[i].tip == 1)
        {
            int x = v[i].x;
            if (a[x] == '0')
            {
                a[x] = '1';
                bool lft = false, rgt = false;
                if (x != 1 and a[x - 1] == '1')
                    lft = true;
                if (x != n and a[x + 1] == '1')
                    rgt = true;
                if (!lft and !rgt)
                {
                    scvmax.insert({x,x});
                    beg[ {x,x}] = i;
                }
                else if (!lft and rgt)
                {
                    pair<int,int> lol = *scvmax.lower_bound({x + 1, 0});
                    vv.push_back(lol);
                    scvmax.erase(lol);
                    scvmax.insert({x, lol.second});
                    beg[ {x,lol.second}] = i;
                }
                else if (lft and !rgt)
                {
                    pair<int,int> lol = *prev(scvmax.lower_bound({x,0}));
                    vv.push_back(lol);
                    scvmax.erase(lol);
                    scvmax.insert({lol.first, x});
                    beg[ {lol.first,x}] = i;
                }
                else
                {
                    pair<int,int> lolr = *scvmax.lower_bound({x + 1,0}), loll = *prev(scvmax.lower_bound({x,0}));
                    vv.push_back(loll);
                    vv.push_back(lolr);
                    scvmax.erase(loll);
                    scvmax.erase(lolr);
                    scvmax.insert({loll.first, lolr.second});
                    beg[ {loll.first, lolr.second}] = i;
                }
            }
            else
            {
                a[x] = '0';
                pair<int,int> pr = *prev(scvmax.lower_bound({x, n + 1}));
                scvmax.erase(pr);
                vv.push_back(pr);
                if (pr.first != x)
                {
                    scvmax.insert({pr.first, x - 1});
                    beg[ {pr.first, x - 1}] = i;
                }
                if (pr.second != x)
                {
                    scvmax.insert({x + 1, pr.second});
                    beg[ {x + 1, pr.second}] = i;
                }
            }
        }
    }
    build_aib2d_stuff();
    scvmax.clear();
    beg.clear();
    s = 0;
    for (int i = 1; i <= n; i++)
        a[i] = a_ret[i];
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == '0')
        {
            if (s != 0)
            {
                scvmax.insert({s, i - 1});
                s = 0;
            }
            s = 0;
        }
        else
        {
            if (s == 0)
                s = i;
        }
    }
    if (s != 0)
        scvmax.insert({s, n});
    for (int i = 1; i <= q; i++)
    {
        if (v[i].tip == 1)
        {
            int x = v[i].x;
            if (a[x] == '0')
            {
                a[x] = '1';
                bool lft = false, rgt = false;
                if (x != 1 and a[x - 1] == '1')
                    lft = true;
                if (x != n and a[x + 1] == '1')
                    rgt = true;
                if (!lft and !rgt)
                {
                    scvmax.insert({x,x});
                    beg[ {x,x}] = i;
                }
                else if (!lft and rgt)
                {
                    pair<int,int> lol = *scvmax.lower_bound({x + 1, 0});
                    update(lol.first, lol.second, i - beg[lol]);
                    scvmax.erase(lol);
                    scvmax.insert({x, lol.second});
                    beg[ {x,lol.second}] = i;
                }
                else if (lft and !rgt)
                {
                    pair<int,int> lol = *prev(scvmax.lower_bound({x,0}));
                    update(lol.first, lol.second, i - beg[lol]);
                    scvmax.erase(lol);
                    scvmax.insert({lol.first, x});
                    beg[ {lol.first,x}] = i;
                }
                else
                {
                    pair<int,int> lolr = *scvmax.lower_bound({x + 1,0}), loll = *prev(scvmax.lower_bound({x,0}));
                    //cout << loll.first << ' ' << loll.second << ' ' << lolr.first << ' ' << lolr.second << endl;
                    update(loll.first, loll.second, i - beg[loll]);
                    update(lolr.first, lolr.second, i - beg[lolr]);
                    scvmax.erase(loll);
                    scvmax.erase(lolr);
                    scvmax.insert({loll.first, lolr.second});
                    beg[ {loll.first, lolr.second}] = i;
                }
            }
            else
            {
                a[x] = '0';
                pair<int,int> pr = *prev(scvmax.lower_bound({x, n + 1}));
                scvmax.erase(pr);
                update(pr.first, pr.second, i - beg[pr]);
                if (pr.first != x)
                {
                    scvmax.insert({pr.first, x - 1});
                    beg[ {pr.first, x - 1}] = i;
                }
                if (pr.second != x)
                {
                    scvmax.insert({x + 1, pr.second});
                    beg[ {x + 1, pr.second}] = i;
                }
            }
        }
        else
        {
            int x = v[i].x, y = v[i].y;
            int vl = query(x, n) - query(x, y - 1);
            if (a[x] == '1')
            {
                pair<int,int> pr = *prev(scvmax.lower_bound({x, n + 1}));
                //cout << i << ' ' << pr.first << ' ' << pr.second << endl;
                if (pr.first <= x and pr.second >= y)
                    vl += i - beg[pr];
            }
            cout << vl << '\n';
        }
    }
    return 0;
}

/**
Ma uit la secventele maximale de 1, eu vreau sa vad in cate momente a fost [x y] inclus intr-o secventa maximala
Daca retin, pentru fiecare secventa maximala, cat dureaza (termin cu ea cand se modifica), vreau suma(timp) pentru secventele care ma includ
Sa zicem ca atunci cand modific o secventa maximala o pun in "DS", o sa adun la raspuns, daca acum sunt intr-o secventa maximala, de cand e ea
Si fac O(N + Q) update-uri de forma: pentru fiecare (x, y) cu L <= x <= y <= R, adauga k si Q query-uri de forma: zi cat e un punct
Adica tehnic bag update cu +k in (L,R), si vreau suma pe dreptunghiul ((1,y), (x, N)) adica ((1,1), (x,N)) - ((1,1), (x, y - 1))
Yayy, aib 2d pe care nu l-am mai implementat vreodata
**/

Compilation message (stderr)

street_lamps.cpp: In function 'int get_pos(int, int)':
street_lamps.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if (st + pas < ps[unde].size() and ps[unde][st + pas] <= y)
      |             ~~~~~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void update(int, int, int)':
street_lamps.cpp:57:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int j = get_pos(i,y); j < ps[i].size(); j += (j & -j))
      |                                    ~~^~~~~~~~~~~~~~

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