Submission #555415

#	Time	Username	Problem	Language	Result	Execution time	Memory
555415		shahriarkhan	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2182 ms	103112 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std ;

//T1 handles sums
//T2 handles, if it has already started or not!

const int N = 3e5 + 5 ;

int ans[N] , type[N] , stat[N] , signs[2] = {1,-1} ;

struct box
{
    int l = 0 , r = 0 , sign = 0 , val = 0 , val2 = 0 , idx = 0 , type = 0 ;
};

bool cmp1(box &a , box &b)
{
    if(a.l!=b.l) return a.l < b.l ;
    return a.type < b.type ;
}

bool cmp2(box &a , box &b)
{
    if(a.r!=b.r) return a.r < b.r ;
    return a.type < b.type ;
}

set<pair<int,int> > S ;

vector<box> v ;

void toggle(int l , int r , int i , int idx , int s)
{
    v.push_back({l,i,signs[s],idx,signs[s^1],idx,1}) ;
    v.push_back({l,r+1,signs[s^1],idx,signs[s],idx,1}) ;
    v.push_back({i+1,i,signs[s^1],idx,signs[s],idx,1}) ;
    v.push_back({i+1,r+1,signs[s],idx,signs[s^1],idx,1}) ;
}

void query(int l , int r , int idx)
{
    v.push_back({l,r-1,1,0,0,idx,2}) ;
}

struct BIT
{
	int bit[N] = {};
	void update(int p,int v) {
	    ++p ;
		for(;p< N; p+= p&-p) bit[p] += v;
	}
    int query(int p) {
        ++p ;
    	int r=0;
    	for(;p>0;p-=p&-p) r += bit[p];
        return r;
    }
    int query(int a,int b) {
    	return query(b) - query(a - 1);
    }
} T1 , T2;

void divide(int low , int high)
{
    if(low==high) return ;
    int mid = (low+high)>>1 ;
    divide(low,mid) , divide(mid+1,high) ;
    vector<int> rem ;
    vector<box> left , right ;
    for(int i = low ; i <= high ; ++i)
    {
        if(i<=mid)
        {
            if(v[i].type==1) left.push_back(v[i]) ;
        }
        else
        {
            if(v[i].type==2) right.push_back(v[i]) ;
        }
    }
    if(left.empty() || right.empty()) return ;
    sort(left.begin(),left.end(),cmp2) ;
    sort(right.begin(),right.end(),cmp2) ;
    int siz_left = left.size() , siz_right = right.size() , cur = 0 ;
    for(int i = 0 ; i < siz_right ; ++i)
    {
        while((cur<siz_left) && (left[cur].r<=right[i].r))
        {
            T1.update(left[cur].idx,left[cur].sign*left[cur].val) ;
            T2.update(left[cur].idx,left[cur].val2) ;
            //cout<<"left:"<<' '<<left[cur].l<<' '<<left[cur].r<<' '<<left[cur].idx<<endl ;
            rem.push_back(cur) ;
            ++cur ;
        }
        //cout<<"right:"<<' '<<right[i].l<<' '<<right[i].r<<' '<<right[i].idx<<' '<<T1.query(1,0,N,0,right[i].idx)<<' '<<T2.query(1,0,N,0,right[i].idx)<<endl ;
        ans[right[i].idx] += (right[i].sign*(T1.query(right[i].idx) + ((T2.query(right[i].idx)*right[i].idx)))) ;
    }
    for(int i : rem)
    {
        T1.update(left[i].idx,-(left[i].sign*left[i].val)) ;
        T2.update(left[i].idx,-left[i].val2) ;
    }
    return ;
}

int main()
{
    int n , q , t_l = -1 ;
    scanf("%d%d",&n,&q) ;
    string s ;
    cin>>s ;
    for(int i = 0 ; i < n ; ++i)
    {
        if(s[i]=='0')
        {
            stat[i+1] = 0 ;
            if(t_l>=0) S.insert({t_l+1,i}) , t_l = -1 ;
        }
        else
        {
            stat[i+1] = 1 ;
            if(t_l==(-1)) t_l = i ;
        }
    }
    if(t_l!=(-1)) S.insert({t_l+1,n}) ;
    for(pair<int,int> p : S)
    {
        int l = p.first , r = p.second ;
        v.push_back({l,0,1,0,1,0,1}) ;
        v.push_back({l,r+1,-1,0,-1,0,1}) ;
        v.push_back({r+1,0,-1,0,-1,0,1}) ;
        v.push_back({r+1,r+1,1,0,1,0,1}) ;
    }
    for(int time = 1 ; time <= q ; ++time)
    {
        string t ;
        cin>>t ;
        if(t=="toggle")
        {
            type[time] = 1 ;
            int idx ;
            scanf("%d",&idx) ;
            stat[idx] ^= 1 ;
            int l = 0 , r = 0 ;
            vector<pair<int,int> > rem ;
            if(stat[idx])
            {
                auto it2 = S.lower_bound({idx+1,0}) ;
                if(it2!=S.end())
                {
                    pair<int,int> cur = *it2 ;
                    if(cur.first==(idx+1))
                    {
                        rem.push_back(cur) ;
                        r = cur.second ;
                    }
                    else r = idx ;
                }
                else r = idx ;
                if(it2!=S.begin())
                {
                    pair<int,int> cur = *(--it2) ;
                    if(cur.second==(idx-1))
                    {
                        rem.push_back(cur) ;
                        l = cur.first ;
                    }
                    else l = idx ;
                }
                else l = idx ;
                for(pair<int,int> p : rem)
                {
                    S.erase(p) ;
                }
                S.insert({l,r}) ;
            }
            else
            {
                auto it = --S.lower_bound({idx+1,0}) ;
                pair<int,int> cur = *it ;
                l = cur.first , r = cur.second ;
                rem.push_back(cur) ;
                for(pair<int,int> p : rem)
                {
                    S.erase(p) ;
                }
                if(l<=(idx-1)) S.insert({l,idx-1}) ;
                if((idx+1)<=r) S.insert({idx+1,r}) ;
            }
            toggle(l,r,idx,time,stat[idx]) ;
        }
        else
        {
            type[time] = 2 ;
            int a , b ;
            scanf("%d%d",&a,&b) ;
            query(a,b,time) ;
        }
    }
    int siz = v.size() ;
    sort(v.begin(),v.end(),cmp1) ;
    divide(0,siz-1) ;
    for(int i = 1 ; i <= q ; ++i)
    {
        if(type[i]==2) printf("%d\n",ans[i]) ;
    }
    return 0 ;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d%d",&n,&q) ;
      |     ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:142:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |             scanf("%d",&idx) ;
      |             ~~~~~^~~~~~~~~~~
street_lamps.cpp:196:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |             scanf("%d%d",&a,&b) ;
      |             ~~~~~^~~~~~~~~~~~~~

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