oj.uz

Submission #92553

# Submission time Handle Problem Language Result Execution time Memory
92553 2019-01-03T11:53:22 Z Nodir_Bobiev Simple game (IZhO17_game) C++14
0 / 100
 6 ms 3832 KB 
# 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);
				l = min(val, h[pos - 1]);
				r = max(val, h[pos - 1]);
				update(l, +1); update(r, -1);
			}
			if(pos != n){
				l = min(h[pos], h[pos + 1]);
				r = max(h[pos], h[pos + 1]);
				update(l, -1); update(r, +1);
				l = min(val, h[pos + 1]);
				r = max(val, h[pos + 1]);
				update(l, +1); update(r, -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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 3832 KB Output is correct
3 Incorrect 6 ms 3832 KB Output isn't correct
4 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 Correct 6 ms 3832 KB Output is correct
3 Incorrect 6 ms 3832 KB Output isn't correct
4 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 Correct 6 ms 3832 KB Output is correct
3 Incorrect 6 ms 3832 KB Output isn't correct
4 Halted 0 ms 0 KB -