답안 #983413

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
983413 2024-05-15T12:06:22 Z vivkostov 가로등 (APIO19_street_lamps) C++14
0 / 100
83 ms 14672 KB
#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[300005],r[300005],br=2;
string s,a[300005];
cell p[30000005];
map<pair<int,int>,int>m;
void start()
{
    int ll=0;
    for(int i=0; i<n; i++)
    {
        if(s[i]=='0')
        {
            if(ll!=i)
            {
                pair<int,int>p;
                p.first=ll+1;
                p.second=i;
                m[p]++;
            }
            ll=i+1;
        }
    }
    if(ll!=n)
    {
        pair<int,int>p;
        p.first=ll+1;
        p.second=n;
        m[p]++;
    }
}
void checkmap()
{
    for(auto i=m.begin(); i!=m.end(); i++)
    {
        cout<<i->first.first<<" "<<i->first.second<<" ";
    }
    cout<<endl;
}
void update2(int l,int r,int ql,int qr,int h,int x)
{
    if(l>qr||r<qr)return;
    if(!p[h].l)
    {
        p[h].l=br;
        p[h].r=br+1;
        br+=2;
    }
    if(l==r&&r==qr)
    {
        p[h].st+=x;
        //cout<<l<<" "<<r<<" "<<p[h].st<<" : ";
        return;
    }
    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(r<qr)return 0;
    if(!p[h].l)
    {
        p[h].l=br;
        p[h].r=br+1;
        br+=2;
    }
    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)return 0;
    if(!p[h].l)
    {
        p[h].l=br;
        p[h].r=br+1;
        p[h].in=br+2;
        br+=3;
    }
    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);
    it--;
    int le=it->first.first,ri=it->first.second,st=it->second;
    cout<<le<<" "<<ri<<endl;
    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);
        it--;
        int 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);
    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 read()
{
    cin>>n>>q>>s;
    for(int i=1; i<=q; i++)
    {
        cin>>a[i]>>l[i];
        if(a[i]=="query")cin>>r[i];
    }
    start();
    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;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 14672 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Incorrect 3 ms 13144 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 13912 KB Output is correct
2 Incorrect 4 ms 13404 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -