oj.uz

Submission #48397

# Submission time Handle Problem Language Result Execution time Memory
48397 2018-05-12T17:21:18 Z aleksami Simple game (IZhO17_game) C++14
0 / 100
 15 ms 14824 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 15 ms 14824 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 15 ms 14824 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 15 ms 14824 KB Output isn't correct
3 Halted 0 ms 0 KB -