Submission #48397

#	Time	Username	Problem	Language	Result	Execution time	Memory
48397		aleksami	Simple game (IZhO17_game)	C++14	0 / 100	15 ms	14824 KiB

game

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXH 1000005

int tree[4*MAXH];
int lazy[4*MAXH];
int a[MAXN];

void push(int node,int left,int right)
{
	if(lazy[node]!=0)
	{
		tree[node]+=lazy[node]*(right-left+1);
		if(left != right)
		{
			lazy[node*2]+=lazy[node];
			lazy[node*2+1]+=lazy[node];
		}
		lazy[node]=0;
	}
}
void update(int node,int left,int right,int l,int r,int val)
{
	push(node,left,right);
	if(left >= l && right <= r)
	{
		lazy[node]+=val;
		push(node,left,right);
		return ;
	}
	int mid=left+right>>1;
	if(l <= mid)update(node*2,left,mid,l,r,val);
	if(r > mid)update(node*2+1,mid+1,right,l,r,val);
	tree[node]=tree[node*2]+tree[node*2+1];
}
int query(int node,int left,int right,int l,int r)
{
	push(node,left,right);
	if(left >= l && right <= r)return tree[node];
	int mid=left+right>>1;
	int ret=0;
	if(l <= mid)ret += query(node*2,left,mid,l,r);
	if(r > mid)ret += query(node*2+1,mid+1,right,l,r);
	return ret;
}


int main() {
	ios_base::sync_with_stdio(false);
	int n,q;
	cin >> n >> q;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for(int i = 0; i < n-1; i++)
	{
		int l = min(a[i],a[i+1]);
		int r = max(a[i],a[i+1]);
		if(l!=r)update(1,1,MAXH-1,l,r,1);
		else update(1,1,MAXH-1,l,r,2);
	}
	while(q--)
	{
		int t;
		cin >> t;
		if(t==1)
		{
			int pos,val;
			cin >> pos >> val;
			pos--;
			int i = pos;
			int l = min(a[i],a[i+1]);
			int r = max(a[i],a[i+1]);
			if(l!=r)update(1,1,MAXH-1,l,r,-1);
			else update(1,1,MAXH-1,l,r,-2);
			a[pos]=val;
			l = min(a[i],a[i+1]);
			r = max(a[i],a[i+1]);
			if(l!=r)update(1,1,MAXH-1,l,r,1);
			else update(1,1,MAXH-1,l,r,2);
		}
		else
		{
			int h;
			cin >> h;
			cout << query(1,1,MAXH-1,h,h) << "\n";
		}
	}
	return 0;
}

Compilation message (stderr)

game.cpp: In function 'void update(int, int, int, int, int, int)':
game.cpp:32:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=left+right>>1;
          ~~~~^~~~~~
game.cpp: In function 'int query(int, int, int, int, int)':
game.cpp:41:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=left+right>>1;
          ~~~~^~~~~~

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