Submission #1070224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070224		alexdd	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	269 ms	59448 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;
struct Fenwick
{
    vector<int> s;
    Fenwick(int n) : s(n+1){}
    int qry(int poz)
    {
        int aux=0;
        for(int i=poz;i<s.size();i+=(i&(-i)))
            aux += s[i];
        return aux;
    }
    void upd(int poz, int newv)
    {
        for(int i=poz;i>0;i-=(i&(-i)))
            s[i] += newv;
    }
};
struct FT2
{
    vector<vector<int>> ys;
    vector<Fenwick> ft;
    FT2(int limx) : ys(limx+1){}
    void fake_upd(int pozx, int pozy)
    {
        for(int i=pozx;i<ys.size();i+=(i&(-i)))
            ys[i].push_back(pozy);
    }
    void init()
    {
        for(auto v:ys)
        {
            sort(v.begin(),v.end());
            ft.push_back(v.size());
        }
    }
    int ind(int x, int y)
    {
        return (int)(lower_bound(ys[x].begin(),ys[x].end(),y) - ys[x].begin() + 1);
    }
    int qry(int pozx, int pozy)
    {
        int aux=0;
        for(int i=pozx;i>0;i-=(i&(-i)))
            aux += ft[i].qry(ind(i,pozy));
        return aux;
    }
    void upd(int pozx, int pozy, int newv)
    {
        for(int i=pozx;i<ys.size();i+=(i&(-i)))
            ft[i].upd(ind(i,pozy),newv);
    }
};

set<pair<pair<int,int>,int>> s;
bool tip[300005];
int cit[300005][2];
signed main()
{
    int n,q;
    cin>>n>>q;
    FT2 old(n),active_sum(n),active_cnt(n);
    vector<bool> init(n+2,0);
    char ch;
    for(int i=1;i<=n;i++)
    {
        cin>>ch;
        if(ch=='1') init[i]=1;
        else init[i]=0;
    }
    vector<bool> stare=init;
    int inc=-1;
    for(int i=1;i<=n;i++)
    {
        if(stare[i]==1)
        {
            if(inc==-1) inc=i;
            if(i==n || stare[i+1]==0)
            {
                s.insert({{inc,i},0});
                active_cnt.fake_upd(inc,i);
                active_sum.fake_upd(inc,i);
                //cout<<inc<<" "<<i<<" in set\n";
                inc=-1;
            }
        }
    }
    string str;
    int a,b;
    for(int i=1;i<=q;i++)
    {
        cin>>str;
        if(str=="toggle")
            tip[i]=0;
        else
            tip[i]=1;
        if(tip[i]==0)
        {
            cin>>cit[i][0];
            a=cit[i][0];
            if(stare[a]==0)
            {
                int le=a,ri=a;
                if(stare[a-1]==1)
                {
                    auto it = prev(s.lower_bound({{a,-1},-1}));
                    le = (*it).first.first;

                    old.fake_upd((*it).first.first,(*it).first.second);
                    active_cnt.fake_upd((*it).first.first,(*it).first.second);
                    active_sum.fake_upd((*it).first.first,(*it).first.second);

                    s.erase(it);
                }
                if(stare[a+1]==1)
                {
                    auto it = s.lower_bound({{a,-1},-1});
                    ri = (*it).first.second;

                    old.fake_upd((*it).first.first,(*it).first.second);
                    active_cnt.fake_upd((*it).first.first,(*it).first.second);
                    active_sum.fake_upd((*it).first.first,(*it).first.second);

                    s.erase(it);
                }
                s.insert({{le,ri},i});

                active_cnt.fake_upd(le,ri);
                active_sum.fake_upd(le,ri);
            }
            else
            {
                auto it = prev(s.lower_bound({{a,n+1},n+1}));
                int le = (*it).first.first, ri = (*it).first.second;

                old.fake_upd(le,ri);
                active_cnt.fake_upd(le,ri);
                active_sum.fake_upd(le,ri);

                s.erase(it);
                if(stare[a-1]==1)
                {
                    s.insert({{le,a-1},i});
                    active_cnt.fake_upd(le,a-1);
                    active_sum.fake_upd(le,a-1);
                }
                if(stare[a+1]==1)
                {
                    s.insert({{a+1,ri},i});
                    active_cnt.fake_upd(a+1,ri);
                    active_sum.fake_upd(a+1,ri);
                }
            }
            stare[a] = 1-stare[a];
        }
        else
            cin>>cit[i][0]>>cit[i][1];
    }
    stare=init;
    s.clear();
    old.init();
    active_cnt.init();
    active_sum.init();
    inc=-1;
    for(int i=1;i<=n;i++)
    {
        if(stare[i]==1)
        {
            if(inc==-1) inc=i;
            if(i==n || stare[i+1]==0)
            {
                s.insert({{inc,i},0});
                active_cnt.upd(inc,i,+1);
                active_sum.upd(inc,i,0);
                inc=-1;
            }
        }
    }
    for(int i=1;i<=q;i++)
    {
        if(tip[i]==0)
        {
            a=cit[i][0];
            if(stare[a]==0)
            {
                int le=a,ri=a;
                if(stare[a-1]==1)
                {
                    auto it = prev(s.lower_bound({{a,-1},-1}));
                    le = (*it).first.first;

                    old.upd((*it).first.first,(*it).first.second,i-(*it).second);
                    active_cnt.upd((*it).first.first,(*it).first.second,-1);
                    active_sum.upd((*it).first.first,(*it).first.second,-(*it).second);

                    s.erase(it);
                }
                if(stare[a+1]==1)
                {
                    auto it = s.lower_bound({{a,-1},-1});
                    ri = (*it).first.second;

                    old.upd((*it).first.first,(*it).first.second,i-(*it).second);
                    active_cnt.upd((*it).first.first,(*it).first.second,-1);
                    active_sum.upd((*it).first.first,(*it).first.second,-(*it).second);

                    s.erase(it);
                }
                s.insert({{le,ri},i});

                active_cnt.upd(le,ri,+1);
                active_sum.upd(le,ri,i);
            }
            else
            {
                auto it = prev(s.lower_bound({{a,n+1},n+1}));
                int le = (*it).first.first, ri = (*it).first.second;

                old.upd(le,ri,i-(*it).second);
                active_cnt.upd(le,ri,-1);
                active_sum.upd(le,ri,-(*it).second);

                s.erase(it);
                if(stare[a-1]==1)
                {
                    s.insert({{le,a-1},i});
                    active_cnt.upd(le,a-1,+1);
                    active_sum.upd(le,a-1,i);
                }
                if(stare[a+1]==1)
                {
                    s.insert({{a+1,ri},i});
                    active_cnt.upd(a+1,ri,+1);
                    active_sum.upd(a+1,ri,i);
                }
            }
            stare[a] = 1-stare[a];
        }
        else
        {
            a=cit[i][0];
            b=cit[i][1];
            b--;
            int rez=0;
            rez += old.qry(a,b);
            rez += active_cnt.qry(a,b)*i - active_sum.qry(a,b);
            cout<<rez<<"\n";
        }
    }
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In member function 'int Fenwick::qry(int)':
street_lamps.cpp:10:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |         for(int i=poz;i<s.size();i+=(i&(-i)))
      |                       ~^~~~~~~~~
street_lamps.cpp: In member function 'void FT2::fake_upd(int, int)':
street_lamps.cpp:27:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(int i=pozx;i<ys.size();i+=(i&(-i)))
      |                        ~^~~~~~~~~~
street_lamps.cpp: In member function 'void FT2::upd(int, int, int)':
street_lamps.cpp:51:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i=pozx;i<ys.size();i+=(i&(-i)))
      |                        ~^~~~~~~~~~

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