Submission #987634

#	Time	Username	Problem	Language	Result	Execution time	Memory
987634		vivkostov	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2814 ms	471020 KiB

street_lamps

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct cell
{
    int l,r,st,in;
};
int n,q,l,r,br=2;
string s,a;
cell p[30000005];
map<pair<int,int>,int>m;
void checkmap()
{
    for(auto i=m.begin(); i!=m.end(); i++)
    {
        cout<<i->first.first<<" "<<i->first.second<<" "<<i->second;
        cout<<endl;
    }
    cout<<m.size()<<endl;
}
void update2(int l,int r,int ql,int qr,int h,int x)
{
    if(l>qr||r<qr)return;
    if(l==r&&r==qr)
    {
        p[h].st+=x;
        //cout<<l<<" "<<r<<" "<<p[h].st<<" : ";
        return;
    }
    if(!p[h].l)
    {
        p[h].l=br;
        p[h].r=br+1;
        br+=2;
    }
    int mi=(l+r)/2;
    update2(l,mi,ql,qr,p[h].l,x);
    update2(mi+1,r,ql,qr,p[h].r,x);
    p[h].st=p[p[h].l].st+p[p[h].r].st;
}
void update1(int l,int r,int ql,int qr,int h,int x)
{
    if(l>ql||r<ql)return;
    if(!p[h].l)
    {
        p[h].l=br;
        p[h].r=br+1;
        p[h].in=br+2;
        br+=3;
    }
    if(l==r&&r==ql)
    {
        //cout<<l<<" "<<r<<" "<<p[h].in<<" | ";
        update2(1,n,ql,qr,p[h].in,x);
        //cout<<endl;
        return;
    }
    int mi=(l+r)/2;
    update1(l,mi,ql,qr,p[h].l,x);
    update1(mi+1,r,ql,qr,p[h].r,x);
    //cout<<l<<" "<<r<<" "<<p[h].in<<" | ";
    update2(1,n,ql,qr,p[h].in,x);
    //cout<<endl;
}
int query2(int l,int r,int ql,int qr,int h)
{
    if(l>=qr)
    {
        return p[h].st;
    }
    if(r<qr||!p[h].l)return 0;
    int mi=(l+r)/2;
    return query2(l,mi,ql,qr,p[h].l)+query2(mi+1,r,ql,qr,p[h].r);
}
int query1(int l,int r,int ql,int qr,int h)
{
    if(l>ql||!p[h].l)return 0;
    if(r<=ql)
    {
        return query2(1,n,ql,qr,p[h].in);
    }
    int mi=(l+r)/2;
    return query1(l,mi,ql,qr,p[h].l)+query1(mi+1,r,ql,qr,p[h].r);
}
void remov(int in,int tim)
{
    pair<int,int>p;
    p.first=in;
    p.second=1000000000;
    auto it=m.upper_bound(p);
    int le,ri,st;
    it--;
    le=it->first.first,ri=it->first.second,st=it->second;
    update1(1,n,le,ri,1,tim-st);
    m.erase(it);
    if(in-1>=le)
    {
        p.first=le;
        p.second=in-1;
        m[p]=tim;
    }
    if(in+1<=ri)
    {
        p.first=in+1;
        p.second=ri;
        m[p]=tim;
    }
    s[in-1]='0';
    //checkmap();
}
void ad(int in,int tim)
{
    int lp=0,rp=0;
    pair<int,int>p;
    if(m.size()>0)
    {
        p.first=in;
        p.second=100000000;
        auto it=m.upper_bound(p);
        int le,ri,st;
        if(it!=m.begin())
        {
            it--;
            le=it->first.first,ri=it->first.second,st=it->second;
            //cout<<in<<" "<<le<<" "<<ri<<" "<<st<<endl;
            if(ri==in-1)
            {
                //cout<<in<<" ";
                update1(1,n,le,ri,1,tim-st);
                m.erase(it);
                lp=le;
            }
        }
        if(it!=m.end())
        {
            it=m.upper_bound(p);
            if(it!=m.end())
            {
                le=it->first.first,ri=it->first.second,st=it->second;
                //cout<<in<<" "<<le<<" "<<ri<<" "<<st<<endl;
                if(le==in+1)
                {
                    //cout<<in<<endl<<endl;
                    update1(1,n,le,ri,1,tim-st);
                    m.erase(it);
                    rp=ri;
                }
            }
        }
    }
    if(!lp)lp=in;
    if(!rp)rp=in;
    p.first=lp;
    p.second=rp;
    m[p]=tim;
    s[in-1]='1';
}
void print(int l,int r,int tim)
{
    if(m.size()==0)
    {
        cout<<query1(1,n,l,r,1)<<endl;
        return;
    }
    pair<int,int>p;
    p.first=l;
    p.second=100000000;
    auto it=m.upper_bound(p);
    if(it==m.begin())
    {
        cout<<query1(1,n,l,r,1)<<endl;
        return;
    }
    it--;
    int le=it->first.first;
    int ri=it->first.second;
    if(le<=l&&ri>=r)
    {
        cout<<query1(1,n,l,r,1)+tim-it->second<<endl;
        //cout<<query1(1,n,l,r,1)<<endl;
    }
    else cout<<query1(1,n,l,r,1)<<endl;
}
void newstart()
{
    for(int i=0; i<n; i++)
    {
        if(s[i]=='1')ad(i+1,1);
    }
}
void read()
{
    cin>>n>>q>>s;
    newstart();
    for(int i=1; i<=q; i++)
    {
        cin>>a>>l;
        if(a=="toggle")
        {
            if(s[l-1]=='0')ad(l,i+1);
            else remov(l,i+1);
        }
        else
        {
            cin>>r;
            print(l,r-1,i+1);
        }
    }
}
int main()
{
    speed();
    read();
    return 0;
}

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