Submission #250939

#	Time	Username	Problem	Language	Result	Execution time	Memory
250939		huuducpro	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3218 ms	156944 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
int n,q,A[300002];
int bb[300002],ll[300002],rr[300002],len[300002];
int ss[300002];
struct query
{
    int type,a,b;
};
query Q[300002];
void update(int i,int val)
{
    for (i;i<=n;i+=i&(-i))
        bb[i]+=val;
}
int get(int i)
{
    int ans=0;
    for (i;i>=1;i-=i&(-i))
        ans+=bb[i];
    return ans;
}
int getl(int a)
{
    int ans=a;
    int d=1;int c=a-1;int t=get(a-1);
    while (d<=c)
    {
        int mid=(d+c)/2;
        if (t-get(mid-1)==a-mid)
        {
            ans=mid;
            c=mid-1;
        }
        else d=mid+1;
    }
    return ans;
}
int getr(int a)
{
    int ans=a;
    int d=a+1;int c=n;int t=get(a);
    while (d<=c)
    {
        int mid=(d+c)/2;
        if (get(mid)-t==mid-a)
        {
            ans=mid;
            d=mid+1;
        }
        else c=mid-1;
    }
    return ans;
}

vector <int> bit[300002],cs[300002],pre[300002],nex[300002];
vector <int> st[300002];
void addr(int a,int b)
{
    for (int i=a;i<=n;i+=i&(-i))
        st[i].push_back(b);
}
void addl(int a,int b)
{
    for (int i=a;i>=1;i-=i&(-i))
        st[i].push_back(b);
}
void build_bit2d()
{
    for (int i=1;i<=n;i++)
    {
        cs[i].push_back(0);
        sort(st[i].begin(),st[i].end());
        for (int j=0;j<st[i].size();j++)
        {
            if (j==0||st[i][j]>st[i][j-1])
                cs[i].push_back(st[i][j]);
        }
        len[i]=cs[i].size()-1;
        cs[i].push_back(1e9);
        bit[i].resize(cs[i].size(),0);
       // for (int j=1;j<=len[i];j++)
           // cout<<cs[i][j]<<' ';cout<<endl;
    }
}
void update_bit2d(int a,int b,int val)
{
    for (int i=a;i<=n;i+=i&(-i))
    {
        int xp=lower_bound(cs[i].begin(),cs[i].end(),b)-cs[i].begin();
        assert(xp>0);
        for (int j=xp;j<=len[i];j+=j&(-j))
            bit[i][j]+=val;
    }
}
int get_bit2d(int a,int b)
{
    int ans=0;
    for (int i=a;i>=1;i-=i&(-i))
    {
        int xp=lower_bound(cs[i].begin(),cs[i].end(),b)-cs[i].begin();
        for (int j=xp;j>=1;j-=j&(-j))
            ans+=bit[i][j];
    }
    return ans;
}
void solve()
{
    cin>>n>>q;
    string s;cin>>s;
    for (int i=1;i<=n;i++)
    {
        if (s[i-1]=='1') update(i,1);
        A[i]=s[i-1]-'0';
    }
    for (int i=1;i<=q;i++)
    {
        string s;cin>>s;
        if (s=="toggle")
        {
            int p;cin>>p;A[p]=1-A[p];
            int l=getl(p);int r=getr(p);
            addr(l,p);addr(p+1,p);
            addr(l,r+1);addr(p+1,r+1);
            Q[i]={0,p,A[p]};
            ll[i]=l;rr[i]=r;
            if (A[p]==0) update(p,-1);
            else update(p,1);
        }
        else
        {
            int a,b;cin>>a>>b;b--;
            addl(a,b);
            Q[i]={1,a,b};
            if (get(b)-get(a-1)==b-a+1) ss[i]=1;
            else ss[i]=0;
        }
    }
    build_bit2d();
    for (int i=1;i<=q;i++)
    {
        if (Q[i].type==0)
        {
            int p=Q[i].a;int l=ll[i];int r=rr[i];
            if (Q[i].b==1)
            {
                update_bit2d(l,p,-i);
                update_bit2d(p+1,p,i);
                update_bit2d(l,r+1,i);
                update_bit2d(p+1,r+1,-i);
            }
            else
            {
                update_bit2d(l,p,i);
                update_bit2d(p+1,p,-i);
                update_bit2d(l,r+1,-i);
                update_bit2d(p+1,r+1,i);
            }
        }
        else
        {
            int a=Q[i].a;int b=Q[i].b;
            long long res=get_bit2d(a,b);
            if (ss[i]==1) res+=i;
            cout<<res<<'\n';
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("lamps2.inp","r",stdin);
   // freopen("lamps2.out","w",stdout);
    solve();
}

Compilation message (stderr)

street_lamps.cpp: In function 'void update(int, int)':
street_lamps.cpp:13:11: warning: statement has no effect [-Wunused-value]
     for (i;i<=n;i+=i&(-i))
           ^
street_lamps.cpp: In function 'int get(int)':
street_lamps.cpp:19:11: warning: statement has no effect [-Wunused-value]
     for (i;i>=1;i-=i&(-i))
           ^
street_lamps.cpp: In function 'void build_bit2d()':
street_lamps.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<st[i].size();j++)
                      ~^~~~~~~~~~~~~

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