Submission #199749

#	Time	Username	Problem	Language	Result	Execution time	Memory
199749		nafis_shifat	Simple game (IZhO17_game)	C++14	100 / 100	589 ms	36972 KiB

game

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define f first
#define s second
using namespace std;

const int mxn=1e6+4;

ll tree[4*mxn]={};
ll lz[4*mxn]={};
void propogate(int b,int e,int mid,int node,int left,int right)
{
	tree[left]+=(mid-b+1)*lz[node];
    lz[left]+=lz[node];

    tree[right]+=(e-mid)*lz[node];
    lz[right]+=lz[node];

    lz[node]=0;
}
ll query(int node,int b,int e,int p)
{
	if(b>p || e<p)return 0;
	if(b==e)return tree[node];

	int m=b+e>>1;
	int l=node<<1;
	int r=l|1;
	propogate(b,e,m,node,l,r);
	
	return query(l,b,m,p)+query(r,m+1,e,p);


    
}
void update(int node, int b,int e,int l,int r,ll v)
{
	if(b>r || e<l)return;
    if(b>=l && e<=r)
    {
    	tree[node]+=(e-b+1)*v;
    	lz[node]+=v;
    	return;
    }

    int mid=b+e>>1;
    int left=node<<1;
    int right=left|1;
    propogate(b,e,mid,node,left,right);
    

    update(left,b,mid,l,r,v);
    update(right,mid+1,e,l,r,v);

}



int main()
{
	int n,q;
	cin>>n>>q;
	int h[n+1];
	for(int i=1;i<=n;i++)cin>>h[i];
    vector<pii> qs;
	for(int i=0;i<q;i++)
	{
		int t;
		cin>>t;
		if(t==1)
		{
			int p,h;
			cin>>p>>h;
			qs.push_back({p,h});
		}
		else
		{
			int h;
			cin>>h;
			qs.push_back({-1,h});
		}
	}


	for(int i=2;i<=n;i++)
	{
		update(1,1,mxn,min(h[i-1],h[i]),max(h[i-1],h[i]),1);

	}




    int ind=0;
	
	for(int i=0;i<qs.size();i++)
	{
		if(qs[i].f==-1)continue;
		for(int j=ind;j<i;j++)
		{
			cout<<query(1,1,mxn,qs[j].s)<<endl;
		}

		ind=i+1;


		int p=qs[i].f;

		if(p>1)
		{
			update(1,1,mxn,min(h[p-1],h[p]),max(h[p-1],h[p]),-1);
			int d=qs[i].s;
			update(1,1,mxn,min(h[p-1],d),max(h[p-1],d),1);

		}
		if(p<n)
		{
			update(1,1,mxn,min(h[p],h[p+1]),max(h[p],h[p+1]),-1);
			int d=qs[i].s;
			update(1,1,mxn,min(h[p+1],d),max(h[p+1],d),1);

		}

		h[p]=qs[i].s;
	}

	for(int i=ind;i<qs.size();i++)cout<<query(1,1,mxn,qs[i].s)<<endl;
	return 0;
}

Compilation message (stderr)

game.cpp: In function 'long long int query(int, int, int, int)':
game.cpp:27:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=b+e>>1;
        ~^~
game.cpp: In function 'void update(int, int, int, int, int, long long int)':
game.cpp:47:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=b+e>>1;
             ~^~
game.cpp: In function 'int main()':
game.cpp:97:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<qs.size();i++)
              ~^~~~~~~~~~
game.cpp:128:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=ind;i<qs.size();i++)cout<<query(1,1,mxn,qs[i].s)<<endl;
                ~^~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51