Submission #903705

#	Time	Username	Problem	Language	Result	Execution time	Memory
903705		Tenis0206	Street Lamps (APIO19_street_lamps)	C++11	100 / 100	1647 ms	99012 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

const int nmax = 3e5;
const int oo = INT_MAX;

int n,q;

int v[nmax + 5];

int t[nmax + 5];
pair<int,int> qry[nmax + 5];

int rez[nmax + 5];

set<pair<pair<int,int>,int>> s_st;
set<pair<pair<int,int>,int>, greater<pair<pair<int,int>,int>>> s_dr;

vector<pair<pair<int,int>,int>> upd[nmax + 5];

int ai[4 * nmax + 5];
int lazy[4 * nmax + 5];

void propag(int nod)
{
    if(lazy[nod] == 0)
    {
        return;
    }
    ai[nod * 2] = ai[nod * 2 + 1] = lazy[nod];
    lazy[nod * 2] = lazy[nod * 2 + 1] = lazy[nod];
    lazy[nod] = 0;
}

void update(int ua, int ub, int val, int nod, int a, int b)
{
    if(ua <= a && ub>=b)
    {
        ai[nod] = val;
        lazy[nod] = val;
        return;
    }
    propag(nod);
    int mij = (a + b) >> 1;
    if(ua <= mij)
    {
        update(ua,ub,val,nod*2,a,mij);
    }
    if(ub > mij)
    {
        update(ua,ub,val,nod*2+1,mij+1,b);
    }
    ai[nod] = max(ai[nod * 2], ai[nod * 2 + 1]);
}

int query(int qa, int qb, int nod, int a, int b)
{
    if(qa <= a && qb >= b)
    {
        return ai[nod];
    }
    propag(nod);
    int mij = (a + b) >> 1;
    if(qa<=mij && qb>mij)
    {
        return max(query(qa,qb,nod*2,a,mij), query(qa,qb,nod*2+1,mij+1,b));
    }
    if(qa<=mij)
    {
        return query(qa,qb,nod*2,a,mij);
    }
    return query(qa,qb,nod*2+1,mij+1,b);
}

vector<int> aib[nmax + 5], aib_lst[nmax + 5];

int ub(int x)
{
    return (x & (-x));
}

void simulate_update(int poz_st, int poz_dr)
{
    for(int i=poz_st;i<=n;i+=ub(i))
    {
        aib_lst[i].push_back(poz_dr);
    }
}

void update_aib(int poz_st, int poz_dr, int val)
{
    for(int i=poz_st; i<=n; i+=ub(i))
    {
        int st = 1;
        int dr = aib_lst[i].size() - 1;
        int poz = 0;
        while(st<=dr)
        {
            int mij = (st + dr) >> 1;
            if(aib_lst[i][mij] <= poz_dr)
            {
                poz = mij;
                st = mij + 1;
            }
            else
            {
                dr = mij - 1;
            }
        }
        for(int j=poz; j<=aib_lst[i].size()-1; j+=ub(j))
        {
            aib[i][j] += val;
        }
    }
}

int query_aib(int poz_st, int poz_dr)
{
    int rez = 0;
    for(int i=poz_st;i>=1;i-=ub(i))
    {
        int st = 1;
        int dr = aib_lst[i].size() - 1;
        int poz = 0;
        while(st<=dr)
        {
            int mij = (st + dr) >> 1;
            if(aib_lst[i][mij] < poz_dr)
            {
                poz = mij;
                st = mij + 1;
            }
            else
            {
                dr = mij - 1;
            }
        }
        for(int j=aib_lst[i].size()-1;j>=1;j-=ub(j))
        {
            rez += aib[i][j];
        }
        for(int j=poz;j>=1;j-=ub(j))
        {
            rez -= aib[i][j];
        }
    }
    return rez;
}

void Remove_segment(int st, int dr, int i)
{
    auto it_st = s_st.lower_bound({{st,dr}, 0});
    auto it_dr = s_dr.lower_bound({{st,dr}, oo});
    int nr = it_st -> second;
    upd[i].push_back({{st,dr}, i - nr});
    s_st.erase(it_st);
    s_dr.erase(it_dr);
}

void Add(int poz, int i)
{
    update(poz,poz,i,1,1,n);
    int st = poz, dr = poz;
    auto it_dr = s_dr.lower_bound({{poz, oo}, 0});
    if(it_dr != s_dr.end() && it_dr->first.second == poz - 1)
    {
        st = it_dr->first.first;
        update(it_dr->first.first, it_dr->first.second, i, 1,1,n);
        Remove_segment(it_dr->first.first, it_dr->first.second, i);
    }
    auto it_st = s_st.lower_bound({{poz, 0}, 0});
    if(it_st != s_st.end() && it_st->first.first == poz + 1)
    {
        dr = it_st->first.second;
        update(it_st->first.first, it_st->first.second, i, 1,1,n);
        Remove_segment(it_st->first.first, it_st->first.second, i);
    }
    s_st.insert({{st,dr},i});
    s_dr.insert({{st,dr},i});
}

void Rem(int poz, int i)
{
    update(poz,poz,oo,1,1,n);
    auto it = s_dr.lower_bound({{poz, oo}, 0});
    int st = it->first.first;
    int dr = it->first.second;
    if(st < poz)
    {
        update(st,poz - 1,i,1,1,n);
    }
    if(dr > poz)
    {
        update(poz+1, dr,i,1,1,n);
    }
    Remove_segment(st, dr, i);
    if(st != poz)
    {
        s_st.insert({{st, poz - 1}, i});
        s_dr.insert({{st, poz - 1}, i});
    }
    if(dr != poz)
    {
        s_st.insert({{poz + 1, dr}, i});
        s_dr.insert({{poz + 1, dr}, i});
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n>>q;
    for(int i=1; i<=n; i++)
    {
        char ch;
        cin>>ch;
        v[i] = ch - '0';
    }
    int st = 1, dr = 0;
    for(int i=1; i<=n; i++)
    {
        if(v[i] == 1)
        {
            dr = i;
        }
        else
        {
            if(st <= dr)
            {
                s_st.insert({{st,dr}, 0});
                s_dr.insert({{st,dr}, 0});
            }
            st = i + 1;
        }
    }
    if(st <= dr)
    {
        s_st.insert({{st,dr}, 0});
        s_dr.insert({{st,dr}, 0});
    }
    for(int i=1; i<=n; i++)
    {
        if(v[i] == 1)
        {
            update(i,i, 0, 1,1,n);
        }
        else
        {
            update(i,i, oo, 1,1,n);
        }
    }
    for(int i=1; i<=q; i++)
    {
        string tip;
        cin>>tip;
        if(tip == "query")
        {
            t[i] = 0;
            cin>>qry[i].first>>qry[i].second;
            --qry[i].second;
            int a = qry[i].first, b = qry[i].second;
            int last = query(a,b,1,1,n);
            if(last != oo)
            {
                rez[i] += i - last;
            }
        }
        else
        {
            t[i] = 1;
            cin>>qry[i].first;
            int poz = qry[i].first;
            if(v[poz] == 0)
            {
                v[poz] = 1;
                Add(poz,i);
            }
            else
            {
                v[poz] = 0;
                Rem(poz,i);
            }
        }
    }
    for(int i=1; i<=q; i++)
    {
        for(auto it : upd[i])
        {
            int st = it.first.first;
            int dr = it.first.second;
            int val = it.second;
            simulate_update(st,dr);
        }
    }
    for(int i=1; i<=n; i++)
    {
        aib_lst[i].push_back(0);
        aib[i].resize(aib_lst[i].size());
        sort(aib_lst[i].begin(),aib_lst[i].end());
    }
    for(int i=1; i<=q; i++)
    {
        if(t[i] == 0)
        {
            int st = qry[i].first, dr = qry[i].second;
            rez[i] += query_aib(st, dr);
            cout<<rez[i]<<'\n';
        }
        else
        {
            for(auto it : upd[i])
            {
                int st = it.first.first;
                int dr = it.first.second;
                int val = it.second;
                update_aib(st,dr,val);
            }
        }
    }
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void update_aib(int, int, int)':
street_lamps.cpp:111:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int j=poz; j<=aib_lst[i].size()-1; j+=ub(j))
      |                        ~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:297:17: warning: unused variable 'val' [-Wunused-variable]
  297 |             int val = it.second;
      |                 ^~~

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