Submission #158452

#	Time	Username	Problem	Language	Result	Execution time	Memory
158452		nafis_shifat	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	1691 ms	239848 KiB

street_lamps

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
using namespace std;
const int inf=1e9+10;
const int mxn=3e5+10;
vector<pii> root[4*mxn];
vector<pair<pii,int>> qrs[4*mxn];
int res[mxn];
struct nod
{
	nod *left,*right;
	int val;
	nod(int v=0,nod *l=NULL,nod *r=NULL):val(v),left(l),right(r){};

	void update(int b,int e,int pos,int v)
	{
		if(b>pos||e<pos)return;
		if(b==e)
		{
			val+=v;
			return;
		}
		int mid=b+e>>1;
		if(b<=pos && pos<=mid)
		{
			if(left==NULL)left=new nod();
			left->update(b,mid,pos,v);
			val=max(val,left->val);
		}
		else
		{
			if(right==NULL)right=new nod();
			right->update(mid+1,e,pos,v);
			val=max(val,right->val);
		}

	}

	int query(int b,int e,int l,int r)
	{
		if(b>r||e<l)return 0;
		if(b>=l&&e<=r)
		{
			return val;
		}
		int mid=b+e>>1;
		if(left==NULL && right==NULL)return 0;
		if(left==NULL)return right->query(mid+1,e,l,r);
		else if(right==NULL) return left->query(b,mid,l,r);

		return max(left->query(b,mid,l,r),right->query(mid+1,e,l,r));

	}	
};


void process(vector<pii> v1,vector<pair<pii,int> > v2)
{
	nod *seg=new nod();
	for(int i=0;i<v1.size();i++)
	{
		seg->update(1,mxn,v1[i].ff,v1[i].ss);
	}

	for(int i=0;i<v2.size();i++)
	{
		res[v2[i].ss]-=seg->query(1,mxn,v2[i].ff.ff,v2[i].ff.ss);
	}
	free(seg);

}




void update(int node,int b,int e,int l,int r,int pos,int pos2=0,int ind=0)
{
	if(b>r||e<l)return;
	
	if(b>=l&&e<=r)
	{
		if(ind==0)
		   root[node].push_back({pos,e-b+1});
		else
			qrs[node].push_back({{pos,pos2},ind});
		return;
	}
	int w=max(l,b)-min(r,e)+1;
	if(ind==0)
	    root[node].push_back({pos,w});
	
	int mid=b+e>>1;
	int left=node<<1;
	int right=left|1;
	update(left,b,mid,l,r,pos,pos2,ind);
	update(right,mid+1,e,l,r,pos,pos2,ind);

}



int tree[4*mxn];


int qr2(int node,int b,int e,int l,int r)
{
    if(b>r||e<l)return inf;
    if(b>=l&&e<=r)return tree[node];
    int m=b+e>>1;
    int lf=node<<1;
    int rf=lf|1;
    return min(qr2(lf,b,m,l,r),qr2(rf,m+1,e,l,r));
}
void upd(int node, int b,int e,int pos,int val)
{
	if(b>pos||e<pos)return;
	if(b==e)
	{
		tree[node]=val;
		return;
	}
    int m=b+e>>1;
    int l=node<<1;
    int r=l|1;
    upd(l,b,m,pos,val);
    upd(r,m+1,e,pos,val);
    tree[node]=min(tree[l],tree[r]);
}



int main()
{
	for(int i=0;i<4*mxn;i++)tree[i]=inf;

	int n,q;
    cin>>n>>q;
    int a[n+1];
    string s;
    cin>>s;
    for(int i=0;i<n;i++)
    {
    	char c=s[i];
    	
    	if(c=='1')a[i+1]=1;
    	else 
    	{
    		a[i+1]=0;
    		upd(1,1,mxn,i+1,1);
    	}
    }

    int tk=0;
    
  


    for(int i=1;i<=q;i++)
    {
    	string s;
    	cin>>s;
    	if(s[0]=='q')
    	{
    		tk++;
    		int x,y;
    		cin>>x>>y;

    		res[tk]=i;
    		int k=qr2(1,1,mxn,x,y-1);
    		if(k!=inf)
    		{
    			res[tk]-=i-k+1;
    			
    		    
    			update(1,1,mxn,1,k-1,x,y-1,tk);
    			continue;
    		}
    	
    		update(1,1,mxn,1,i,x,y-1,tk);
    	}
    	else
    	{
    		int x;
    		cin>>x;
    		if(a[x]==1)
    		{
    			upd(1,1,mxn,x,i+1);
    			a[x]=0;
    			continue;
    		}
    		int k=qr2(1,1,mxn,x,x);
    		upd(1,1,mxn,x,inf);

    		update(1,1,mxn,k,i,x,0,0);
    		a[x]=1;


    	}
    }
    for(int i=1;i<4*mxn;i++)
    {
    	if(qrs[i].size()>0)process(root[i],qrs[i]);

    }

    for(int i=1;i<=tk;i++)cout<<res[i]<<endl;
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In constructor 'nod::nod(int, nod*, nod*)':
street_lamps.cpp:15:6: warning: 'nod::val' will be initialized after [-Wreorder]
  int val;
      ^~~
street_lamps.cpp:14:7: warning:   'nod* nod::left' [-Wreorder]
  nod *left,*right;
       ^~~~
street_lamps.cpp:16:2: warning:   when initialized here [-Wreorder]
  nod(int v=0,nod *l=NULL,nod *r=NULL):val(v),left(l),right(r){};
  ^~~
street_lamps.cpp: In member function 'void nod::update(int, int, int, int)':
street_lamps.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=b+e>>1;
           ~^~
street_lamps.cpp: In member function 'int nod::query(int, int, int, int)':
street_lamps.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=b+e>>1;
           ~^~
street_lamps.cpp: In function 'void process(std::vector<std::pair<int, int> >, std::vector<std::pair<std::pair<int, int>, int> >)':
street_lamps.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v1.size();i++)
              ~^~~~~~~~~~
street_lamps.cpp:68:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v2.size();i++)
              ~^~~~~~~~~~
street_lamps.cpp: In function 'void update(int, int, int, int, int, int, int, int)':
street_lamps.cpp:95:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=b+e>>1;
          ~^~
street_lamps.cpp: In function 'int qr2(int, int, int, int, int)':
street_lamps.cpp:112:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=b+e>>1;
           ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int)':
street_lamps.cpp:125:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=b+e>>1;
           ~^~

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