oj.uz

Submission #92538

# Submission time Handle Problem Language Result Execution time Memory
92538 2019-01-03T11:16:28 Z Nodir_Bobiev Simple game (IZhO17_game) C++14
100 / 100
 357 ms 9564 KB 
# include <iostream>

using namespace std;

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

int TREE[3 * 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(tr < l)
		return;
	
	if(tl > r)
		return;
	
	//cout << l << ' ' << r << ' ' << tl << ' ' << tr << ' ' << pos << ' ' << x << endl;
	if(tl >= l && tr <= r){
		TREE[pos] += x;
		//cout << "True" << endl;
	}
	else{
		int tm = (tl + tr) >> 1;
		
		update(l, r, tl, tm, (pos << 1), x);
		
		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));
	}
}
void printTREE()
{
	for (int i = 1; i <= 20; i++)
		cout << TREE[i] << ' ';
		
	cout << endl;
}


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

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 9 ms 6520 KB Output is correct
3 Correct 9 ms 6392 KB Output is correct
4 Correct 10 ms 6520 KB Output is correct
5 Correct 10 ms 6520 KB Output is correct
6 Correct 10 ms 6648 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 9 ms 6520 KB Output is correct
3 Correct 9 ms 6392 KB Output is correct
4 Correct 10 ms 6520 KB Output is correct
5 Correct 10 ms 6520 KB Output is correct
6 Correct 10 ms 6648 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 210 ms 888 KB Output is correct
9 Correct 304 ms 9564 KB Output is correct
10 Correct 305 ms 9552 KB Output is correct
11 Correct 199 ms 888 KB Output is correct
12 Correct 259 ms 1764 KB Output is correct
13 Correct 238 ms 1392 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 9 ms 6520 KB Output is correct
3 Correct 9 ms 6392 KB Output is correct
4 Correct 10 ms 6520 KB Output is correct
5 Correct 10 ms 6520 KB Output is correct
6 Correct 10 ms 6648 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 210 ms 888 KB Output is correct
9 Correct 304 ms 9564 KB Output is correct
10 Correct 305 ms 9552 KB Output is correct
11 Correct 199 ms 888 KB Output is correct
12 Correct 259 ms 1764 KB Output is correct
13 Correct 238 ms 1392 KB Output is correct
14 Correct 353 ms 9180 KB Output is correct
15 Correct 353 ms 9336 KB Output is correct
16 Correct 348 ms 9208 KB Output is correct
17 Correct 357 ms 9464 KB Output is correct
18 Correct 350 ms 9364 KB Output is correct