oj.uz

Submission #92556

# Submission time Handle Problem Language Result Execution time Memory
92556 2019-01-03T11:56:19 Z Nodir_Bobiev Simple game (IZhO17_game) C++14
100 / 100
 182 ms 5340 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()
{
	ios_base::sync_with_stdio(false);
	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 5 ms 3960 KB Output is correct
3 Correct 5 ms 3964 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 5 ms 3960 KB Output is correct
7 Correct 4 ms 380 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 5 ms 3960 KB Output is correct
3 Correct 5 ms 3964 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 5 ms 3960 KB Output is correct
7 Correct 4 ms 380 KB Output is correct
8 Correct 159 ms 996 KB Output is correct
9 Correct 182 ms 5272 KB Output is correct
10 Correct 182 ms 5340 KB Output is correct
11 Correct 157 ms 992 KB Output is correct
12 Correct 161 ms 1528 KB Output is correct
13 Correct 163 ms 1356 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 5 ms 3960 KB Output is correct
3 Correct 5 ms 3964 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 5 ms 3960 KB Output is correct
7 Correct 4 ms 380 KB Output is correct
8 Correct 159 ms 996 KB Output is correct
9 Correct 182 ms 5272 KB Output is correct
10 Correct 182 ms 5340 KB Output is correct
11 Correct 157 ms 992 KB Output is correct
12 Correct 161 ms 1528 KB Output is correct
13 Correct 163 ms 1356 KB Output is correct
14 Correct 133 ms 5112 KB Output is correct
15 Correct 136 ms 4928 KB Output is correct
16 Correct 131 ms 4860 KB Output is correct
17 Correct 139 ms 4984 KB Output is correct
18 Correct 141 ms 4984 KB Output is correct