제출 #158300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
158300		nafis_shifat	가로등 (APIO19_street_lamps)	C++14	0 / 100	2260 ms	358892 KiB

street_lamps

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int inf=1e9+10;
const int mxn=3e5+10;
struct nod
{
	nod *left,*right;
	int val;
	nod(int v=-1,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=max(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 -1;
		if(b>=l&&e<=r)
		{
			return val;
		}
		int mid=b+e>>1;
		if(left==NULL && right==NULL)return -1;
		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));

	}	
}*root[4*mxn];

int query(int node,int b,int e,int t1,int t2,int l,int r)
{
	if(b>t2||e<t1)return 0;
	if(root[node]==NULL)return 0;
	if(b>=t1 && e<=t2)
	{
		return root[node]->query(1,mxn,l,r);
	}
	int mid=b+e>>1;
	int lf=node<<1;
	int rf=lf|1;

	int k=root[node]->query(1,mxn,l,r);
	if(k==0)return 0;
	else if(k==(e-b+1))return min(t2,e)-max(t1,b)+1;
	return query(lf,b,mid,t1,t2,l,r)+query(rf,mid+1,e,t1,t2,l,r);

}
void update(int node,int b,int e,int l,int r,int pos)
{
	if(b>r||e<l)return;
	if(root[node]==NULL)root[node]=new nod();
	if(b>=l&&e<=r)
	{
		root[node]->update(1,mxn,pos,(e-b+1));
		return;
	}
	root[node]->update(1,mxn,pos,min(r,e)-max(b,l)+1);
	int mid=b+e>>1;
	int left=node<<1;
	int right=left|1;
	update(left,b,mid,l,r,pos);
	update(right,mid+1,e,l,r,pos);

}








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);
    	}
    }


    for(int i=1;i<=q;i++)
    {
    	string s;
    	cin>>s;
    	if(s[0]=='q')
    	{
    		int x,y;
    		cin>>x>>y;
    		int k=qr2(1,1,mxn,x,y-1);
    		if(k!=inf)
    		{
    		    
    			int off=query(1,1,mxn,1,k-1,x,y-1);
    			cout<<k-off-1<<endl;
    			continue;
    		}
    	
    		cout<<i-query(1,1,mxn,1,i,x,y-1)<<endl;
    	}
    	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);
    		a[x]=1;


    	}
    }



	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In constructor 'nod::nod(int, nod*, nod*)':
street_lamps.cpp:10:6: warning: 'nod::val' will be initialized after [-Wreorder]
  int val;
      ^~~
street_lamps.cpp:9:7: warning:   'nod* nod::left' [-Wreorder]
  nod *left,*right;
       ^~~~
street_lamps.cpp:11:2: warning:   when initialized here [-Wreorder]
  nod(int v=-1,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:21: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:44:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=b+e>>1;
           ~^~
street_lamps.cpp: In function 'int query(int, int, int, int, int, int, int)':
street_lamps.cpp:62:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=b+e>>1;
          ~^~
street_lamps.cpp: In function 'void update(int, int, int, int, int, int)':
street_lamps.cpp:82: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:104: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:117: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