Submission #92538

#	Time	Username	Problem	Language	Result	Execution time	Memory
92538		Nodir_Bobiev	Simple game (IZhO17_game)	C++14	100 / 100	357 ms	9564 KiB

game

# include <iostream>

using namespace std;

const int N = 1e5 + 100;
const int M = 1e6 + 100;

int TREE[3 * M];
int h[N];
int n, m;

void update(int l, int r, int tl, int tr, int pos, int x)
{
	if(tl > tr)
		return;
	
	if(tr < l)
		return;
	
	if(tl > r)
		return;
	
	//cout << l << ' ' << r << ' ' << tl << ' ' << tr << ' ' << pos << ' ' << x << endl;
	if(tl >= l && tr <= r){
		TREE[pos] += x;
		//cout << "True" << endl;
	}
	else{
		int tm = (tl + tr) >> 1;
		
		update(l, r, tl, tm, (pos << 1), x);
		
		update(l, r, tm + 1, tr, ((pos << 1) + 1), x);
	}
}

int get(int tl, int tr, int H, int pos)
{
	if(tl == tr)
		return TREE[pos];
	
	if(tl > tr) 
		return 0;
	
	else{
		int tm = (tl + tr) >> 1;
	
		if(tl <= H && tm >= H)
			return TREE[pos] + get(tl, tm, H, (pos << 1));
		
		else
			return TREE[pos] + get(tm + 1, tr, H, ((pos << 1) + 1));
	}
}
void printTREE()
{
	for (int i = 1; i <= 20; i++)
		cout << TREE[i] << ' ';
		
	cout << endl;
}


int main()
{
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> h[i];
	
	
	for (int i = 1; i < n; i++){
		int l = min(h[i], h[i + 1]);
		int r = max(h[i], h[i + 1]);
		update(l, r, 1, M, 1, +1);
	}
	
	
	while(m--){
		int t;
		cin >> t;
		if(t == 1){
			int pos, val, l, r;
			cin >> pos >> val;
			
			if(pos != 1){
				
				l = min(h[pos], h[pos - 1]);
				r = max(h[pos], h[pos - 1]);
				update(l, r, 1, M, 1, -1);
				
				l = min(val, h[pos - 1]);
				r = max(val, h[pos - 1]);
				update(l, r, 1, M, 1, +1);
			}
			
			if(pos != n){
				
				l = min(h[pos], h[pos + 1]);
				r = max(h[pos], h[pos + 1]);
				update(l, r, 1, M, 1, -1);
				
				l = min(val, h[pos + 1]);
				r = max(val, h[pos + 1]);
				update(l, r, 1, M, 1, +1);
			}
			h[pos] = val;
		}
		
		else{
			int H;
			cin >> H;
			cout << get(1, M, H, 1) << endl	;
		}
	}
	/*
	while(true){
		int l, r;
		cin >> l >> r;
		update(l, r, 1, M, 1, +1);
		printTREE();
	}
	*/
}
/*

3 3
1 5 1
2 3
1 1 5
2 3

*/

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