Submission #979027

#	Time	Username	Problem	Language	Result	Execution time	Memory
979027		Kenjikrab	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	5068 ms	29576 KiB

street_lamps

// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
int const n_max=3e5+10;

typedef array<int,4> arr4;
set<int> zero;
arr4 arr[4*n_max];
vector<int> ans(4*n_max,-1);
int cnt=0;
int fen[4*n_max];
void upd(int idx,int val)
{
    for(int i=idx;i<4*n_max;i+=i&-i)fen[i]+=val;
}
int qr(int idx)
{
    int ret=0;
    for(int i=idx;i>0;i-=i&-i)ret+=fen[i];
    return ret;
}
void sol(int l,int r)
{
    if(l>=r)return;
    int mid=(l+r)>>1;
    sol(l,mid);sol(mid+1,r);
    
    
    int p=l;
    for(int i=mid+1;i<=r;i++)
    {
        if(arr[i][2]!=0)continue;
        while(p<=mid&&arr[p][1]>=arr[i][1]){upd(arr[p][3],arr[p][2]);p++;}
        ans[arr[i][3]]+=qr(arr[i][3]);
    }
    for(int i=l;i<p;i++)
    {
        upd(arr[i][3],-arr[i][2]);
    }
    inplace_merge(arr+l,arr+mid+1,arr+r+1,[&](const arr4 &a,const arr4 &b)
    {return a[1]>b[1];});
}
signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    zero.insert(0);
    s=" "+s;
    for(int i=1;i<=n;i++)
    { 
        s[i]-='0';
        if(s[i]==0)zero.insert(i);
    }
    zero.insert(n+1);
    for(int i=1;i<=q;i++)
    {
        string com;
        cin>>com;
        if(com[0]=='q')
        {
            int a,b;
            cin>>a>>b;
            b--;
            arr[cnt++]={a,b,0,i};
            if(*lower_bound(zero.begin(),zero.end(),a)<=b)ans[i]=0;
            else ans[i]=i;
        }
        else
        {
            int a;
            cin>>a;
            if(s[a])
            {
                auto it=upper_bound(zero.begin(),zero.end(),a);
                int l=*prev(it),m=a,r=*it;
                arr[cnt++]={l+1,r-1,i,i};
                arr[cnt++]={l+1,m-1,-i,i};
                arr[cnt++]={m+1,r-1,-i,i};
                zero.insert(a);
            }
            else
            {
                auto it=find(zero.begin(),zero.end(),a);
                int l=*prev(it),m=a,r=*next(it);
                arr[cnt++]={l+1,r-1,-i,i};
                arr[cnt++]={l+1,m-1,i,i};
                arr[cnt++]={m+1,r-1,i,i};
                zero.erase(it);
            }
            s[a]^=1;
        }
    }
    cout<<endl;
    sort(arr, arr+cnt, [&](const arr4 &a, const arr4 &b)
    {return a[0]^b[0] ? a[0]<b[0] : ((a[1]!=b[1])? a[1]>b[1]:(b[2]==0)); });
    sol(0,cnt-1);
    for(int i=1;i<=q;i++)
    {
        if(ans[i]==-1)continue;
        else cout<<ans[i]<<"\n";
    }
    return 0;
}

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