oj.uz

Submission #92533

# Submission time Handle Problem Language Result Execution time Memory
92533 2019-01-03T10:59:03 Z Nodir_Bobiev Simple game (IZhO17_game) C++14
0 / 100
 3 ms 888 KB 
# include <iostream>

using namespace std;

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

int TREE[2 * 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(tl >= l && tr <= r)TREE[pos] += x;
	else{
		int tm = (tl + tr) >> 1;
		
		if(tl <= r && tm >= l)
			update(l, r, tl, tm, (pos << 1), x);
		
		if(tm + 1 <= r && tr >= l)
			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));
		}
	}
}

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;
			cin >> pos >> val;
			if(pos != 1){
				int l = min(h[pos], h[pos - 1]);
				int r = max(h[pos], h[pos - 1]);
				update(l, r, 1, M, 1, -1);
			}
			if(pos != n){
				int l = min(h[pos], h[pos + 1]);
				int r = max(h[pos], 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	;
		}
	}
	
}
/*

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 Runtime error 3 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 Runtime error 3 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 Runtime error 3 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -