Submission #986759

#	Time	Username	Problem	Language	Result	Execution time	Memory
986759		vivkostov	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	206 ms	97956 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[3000005],r[3000005],br=2;
string s,a[3000005];
cell p[20000005];
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<<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;
        if(br>=20000000)exit(0);
    }
    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(br>=20000000)exit(0);
    }
    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(r<qr||!p[h].l)return 0;
    if(l>=qr)
    {
        return p[h].st;
    }
    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+1);
    m.erase(it);
    if(in-1>=le)
    {
        p.first=le;
        p.second=in-1;
        m[p]=tim+1;
    }
    if(in+1<=ri)
    {
        p.first=in+1;
        p.second=ri;
        m[p]=tim+1;
    }
    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;
            if(ri==in-1)
            {
                update1(1,n,le,ri,1,tim-st+1);
                m.erase(it);
                lp=le;
            }
            it++;
        }
        if(it!=m.end())
        {
            le=it->first.first,ri=it->first.second,st=it->second;
            if(le==in+1)
            {
                update1(1,n,le,ri,1,tim-st+1);
                m.erase(it);
                rp=ri;
            }
        }
    }
    if(!lp)lp=in;
    if(!rp)rp=in;
    p.first=lp;
    p.second=rp;
    m[p]=tim+1;
    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+1<<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,0);
    }
}
void read()
{
    cin>>n>>q>>s;
    for(int i=1; i<=q; i++)
    {
        cin>>a[i]>>l[i];
        if(a[i]=="query")cin>>r[i];
    }
    newstart();
    for(int i=1; i<=q; i++)
    {
        if(a[i]=="toggle")
        {
            if(s[l[i]-1]=='0')ad(l[i],i);
            else remov(l[i],i);
        }
        else
        {
            print(l[i],r[i]-1,i);
        }
    }
}
int main()
{
    speed();
    read();
    return 0;
}

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