oj.uz

Submission #92555

# Submission time Handle Problem Language Result Execution time Memory
92555 2019-01-03T11:55:40 Z Nodir_Bobiev Simple game (IZhO17_game) C++14
100 / 100
 238 ms 5368 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, +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.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 Correct 6 ms 3960 KB Output is correct
4 Correct 6 ms 3964 KB Output is correct
5 Correct 6 ms 3832 KB Output is correct
6 Correct 6 ms 3960 KB Output is correct
7 Correct 5 ms 376 KB Output is correct

Subtask #2
27.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 Correct 6 ms 3960 KB Output is correct
4 Correct 6 ms 3964 KB Output is correct
5 Correct 6 ms 3832 KB Output is correct
6 Correct 6 ms 3960 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 199 ms 1020 KB Output is correct
9 Correct 238 ms 5240 KB Output is correct
10 Correct 236 ms 5368 KB Output is correct
11 Correct 195 ms 1012 KB Output is correct
12 Correct 219 ms 1528 KB Output is correct
13 Correct 224 ms 1400 KB Output is correct

Subtask #3
51.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 Correct 6 ms 3960 KB Output is correct
4 Correct 6 ms 3964 KB Output is correct
5 Correct 6 ms 3832 KB Output is correct
6 Correct 6 ms 3960 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 199 ms 1020 KB Output is correct
9 Correct 238 ms 5240 KB Output is correct
10 Correct 236 ms 5368 KB Output is correct
11 Correct 195 ms 1012 KB Output is correct
12 Correct 219 ms 1528 KB Output is correct
13 Correct 224 ms 1400 KB Output is correct
14 Correct 206 ms 4896 KB Output is correct
15 Correct 203 ms 4956 KB Output is correct
16 Correct 206 ms 4988 KB Output is correct
17 Correct 206 ms 5052 KB Output is correct
18 Correct 203 ms 4988 KB Output is correct