Submission #92555

#	Time	Username	Problem	Language	Result	Execution time	Memory
92555		Nodir_Bobiev	Simple game (IZhO17_game)	C++14	100 / 100	238 ms	5368 KiB

game

# include <iostream>

using namespace std;

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

int n, m, t;
int h[N];
int d[M + 1];

void update(int x, int s)
{
	while(x <= M){
		d[x] += s;
		x += (x & -x);
	}
}

int get(int x){
	int s = 0;
	while(x > 0){
		s += d[x];
		x -= (x & -x);
	}
	return s;
}

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

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

*/

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