Submission #713945

#	Time	Username	Problem	Language	Result	Execution time	Memory
713945		HuyQuang_re_Zero	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2158 ms	313716 KiB

street_lamps

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 300002
#define II pair <int,int>
#define fst first
#define snd second
using namespace std;
set <int> off;
map <II,int> Begin;
int n,i,j,l,r,u,v,q,lg,pos;
string s;
struct trie
{
    int sum=0;
    trie *c[2];
};
trie *bit[N];
void add(trie *u,int x,int k)
{
    for(int i=lg;i>=0;i--)
    {
        if(u->c[(x>>i)&1]==NULL) u->c[(x>>i)&1]=new trie();
        u=u->c[(x>>i)&1];
        u->sum+=k;
    }
}
int cal(trie *u,int x)
{
    int res=0;
    for(int i=lg;i>=0;i--)
    {
        if(!((x>>i)&1))
        {
            if(u->c[1]!=NULL) res+=u->c[1]->sum;
        }
        if(u->c[(x>>i)&1]==NULL) return res;
        u=u->c[(x>>i)&1];
    }
    return res+u->sum;
}
void update(int i,int x,int k)
{
    while(i<=n) add(bit[i],x,k),i+=(i & -i);
}
int get(int i,int x)
{
    int res=0;
    while(i>=1) res+=cal(bit[i],x),i-=(i & -i);
    return res;
}
int main()
{
 //   freopen("ntu.inp","r",stdin);
 //   freopen("ntu.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>q>>s; s=" "+s;
    lg=trunc(log2(n));
    off.insert(0); off.insert(n+1);
    for(i=1;i<=n;i++)
    {
        bit[i]=new trie();
        if(s[i]=='0') off.insert(i),pos=i;
        else if(i==n || s[i+1]=='0') Begin[{ pos+1,i }]=0;
    }
    for(j=1;j<=q;j++)
    {
        string type; cin>>type;
        if(type=="toggle")
        {
            cin>>i;
            if(s[i]=='0')
            {
                s[i]='1'; off.erase(i);
                set <int>::iterator it=off.lower_bound(i); it--;
                l=(*it)+1; r=*(off.upper_bound(i))-1;
                if(l<i) update(l,i-1,j-Begin[{ l,i-1 }]);
                if(r>i) update(i+1,r,j-Begin[{ i+1,r }]);
                Begin[{ l,r }]=j;
            }
            else if(s[i]=='1')
            {
                s[i]='0'; off.insert(i);
                set <int>::iterator it=off.lower_bound(i); it--;
                l=(*it)+1; r=*(off.upper_bound(i))-1;
                if(l<i) Begin[{ l,i-1 }]=j;
                if(r>i) Begin[{ i+1,r }]=j;
                update(l,r,j-Begin[{ l,r }]);
            }
        }
        else
        {
            cin>>l>>r; r--;
            set <int>::iterator it=off.upper_bound(r);
            int u,v=*it;
            it--; u=*it;
            u++; v--;
            if(u<=l && r<=v) cout<<get(l,r)+j-Begin[{ u,v }]<<'\n';
            else cout<<get(l,r)<<'\n';
        }
    }
}

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