Submission #758460

#	Time	Username	Problem	Language	Result	Execution time	Memory
758460		bgnbvnbv	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	856 ms	134208 KiB

street_lamps

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=int;
const ll maxN=3e5+10;
///const ll inf=1e18;
const ll mod=1e9+7;
ll n;
struct off2dseg
{
    struct BIT
    {
        vector<ll> bit;
        void upd(ll pos,ll val)
        {
            while(pos<bit.size())
            {
                bit[pos]+=val;
                pos+=pos&(-pos);
            }
        }
        ll get(ll i)
        {
            ll ans=0;
            while(i>0)
            {
                ans+=bit[i];
                i-=i&(-i);
            }
            return ans;
        }
    }bit[4*maxN];
    vector<ll>vec[4*maxN];
    void fupdate(ll x1,ll y1,ll x2,ll y2,ll id=1,ll l=1,ll r=n)
    {
        if(x2<l||r<x1) return;
        if(x1<=l&&r<=x2)
        {
            vec[id].pb(y1);
            vec[id].pb(y2+1);
            return;
        }
        ll mid=l+r>>1;
        fupdate(x1,y1,x2,y2,id*2,l,mid);
        fupdate(x1,y1,x2,y2,id*2+1,mid+1,r);
    }
    void build()
    {
        for(int i=1;i<=4*n;i++)
        {
            sort(vec[i].begin(),vec[i].end());
            bit[i].bit.resize(vec[i].size()+1);
        }
    }
    void update(ll x1,ll y1,ll x2,ll y2,ll v,ll id=1,ll l=1,ll r=n)
    {
        if(x2<l||r<x1) return;
        if(x1<=l&&r<=x2)
        {
            y1=lower_bound(vec[id].begin(),vec[id].end(),y1)-vec[id].begin()+1;
            y2=lower_bound(vec[id].begin(),vec[id].end(),y2+1)-vec[id].begin()+1;
            bit[id].upd(y1,v);
            bit[id].upd(y2,-v);
            return;
        }
        ll mid=l+r>>1;
        update(x1,y1,x2,y2,v,id*2,l,mid);
        update(x1,y1,x2,y2,v,id*2+1,mid+1,r);
    }
    ll get(ll x,ll y,ll id=1,ll l=1,ll r=n)
    {
        ll p=upper_bound(vec[id].begin(),vec[id].end(),y)-vec[id].begin();
        p=bit[id].get(p);
        if(l==r) return p;
        ll mid=l+r>>1;
        if(x<=mid) return p+get(x,y,id*2,l,mid);
        else return p+get(x,y,id*2+1,mid+1,r);
    }
}tree;
set<int> s;
ll q;
char c[maxN];
ll a[maxN],r[maxN],t[maxN];
string T[maxN];
struct qq
{
    ll i,l,r,v;
};
vector<qq> quer;
set<int> ::iterator it;
ll x[maxN],y[maxN];
ll ans[maxN];
void solve()
{
    cin >> n >> q ;
    for(int i=1;i<=n;i++)
    {
        cin >> c[i];
        a[i]=c[i]-'0';
    }
    for(int i=1;i<=n;i++)
    {
        ll j=i;
        if(a[i]==0) continue;
        while(j<=n&&a[j]==a[i])
        {
            j++;
        }
        s.insert(i);
        r[i]=j-1;
        t[i]=0;
        i=j-1;
    }
    for(int i=1;i<=q;i++)
    {
        cin >> T[i];
        if(T[i]=="toggle")
        {
            ll p;
            cin >> p;
            if(a[p]==1)
            {
                it=s.upper_bound(p);
                it--;
                ll L=*it;
                ll R=r[L];
                ll T=t[L];
                s.erase(it);
                tree.fupdate(L,L,R,R);
                quer.pb({i,L,R,i-T});
                if(L<=p-1)
                {
                    r[L]=p-1;
                    t[L]=i;
                    s.insert(L);
                }
                if(p+1<=R)
                {
                    r[p+1]=R;
                    t[p+1]=i;
                    s.insert(p+1);
                }
            }
            else
            {
                it=s.lower_bound(p);
                ll L=p,R=p;
                vector<ll> xoa;
                if(it!=s.end()&&*it==p+1)
                {
                    tree.fupdate(p+1,p+1,r[p+1],r[p+1]);
                    R=r[p+1];
                    quer.pb({i,p+1,r[p+1],i-t[p+1]});
                    xoa.pb(p+1);
                }
                if(it!=s.begin())
                {
                    it--;
                    if(r[*it]==p-1)
                    {
                        tree.fupdate(*it,*it,p-1,p-1);
                        L=*it;
                        quer.pb({i,L,p-1,i-t[L]});
                        xoa.pb(L);
                    }
                }
                for(auto zz:xoa) s.erase(zz);
                r[L]=R;
                t[L]=i;
                s.insert(L);
            }
            a[p]^=1;
        }
        else
        {
            cin >> x[i] >> y[i];
            y[i]--;
            it=s.upper_bound(y[i]);
            if(it!=s.begin()&&a[y[i]]==1)
            {
                it--;
                if(*it<=x[i])
                {
                    ans[i]+=i-t[*it];
                }
            }
        }
    }
    //cout << ans[4]<<'\n';
    tree.build();
    ll j=0;
    for(int i=1;i<=q;i++)
    {
        while(j<quer.size()&&quer[j].i<=i)
        {
            ll L=quer[j].l;
            ll R=quer[j].r;
            ll v=quer[j].v;
            tree.update(L,L,R,R,v);
            j++;
        }
        if(T[i]=="query")
        {

            ans[i]+=tree.get(x[i],y[i]);
            cout << ans[i]<<'\n';
        }
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void off2dseg::BIT::upd(ll, ll)':
street_lamps.cpp:21:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             while(pos<bit.size())
      |                   ~~~^~~~~~~~~~~
street_lamps.cpp: In member function 'void off2dseg::fupdate(ll, ll, ll, ll, ll, ll, ll)':
street_lamps.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         ll mid=l+r>>1;
      |                ~^~
street_lamps.cpp: In member function 'void off2dseg::update(ll, ll, ll, ll, ll, ll, ll, ll)':
street_lamps.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         ll mid=l+r>>1;
      |                ~^~
street_lamps.cpp: In member function 'll off2dseg::get(ll, ll, ll, ll, ll)':
street_lamps.cpp:80:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         ll mid=l+r>>1;
      |                ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:199:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |         while(j<quer.size()&&quer[j].i<=i)
      |               ~^~~~~~~~~~~~

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