oj.uz

답안 #536684

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
536684 2022-03-13T20:31:05 Z blue Simple game (IZhO17_game) C++17
100 / 100
 95 ms 11240 KB 
#include <iostream>
#include <vector>
using namespace std;

using vi = vector<int>;

const int mx = (1<<20);

vi st(mx<<1, 0);

void add(int l, int r, int v)
{
	if(r < l) swap(l, r);
	l += mx;
	r += mx+1;
	while(l < r)
	{
		if(l & 1)
		{
			st[l] += v;
			l++;
		}

		if(r & 1)
		{
			r--;
			st[r] += v;
		}

		l >>= 1;
		r >>= 1;
	}
}

int get(int i)
{
	i += mx;
	int res = 0;
	while(i >= 1)
	{
		res += st[i];
		i >>= 1;
	}
	return res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;

	vi h(1+N);
	for(int i = 1; i <= N; i++) cin >> h[i];

	for(int i = 1; i < N; i++)
		add(h[i], h[i+1], 1);

	for(int j = 1; j <= M; j++)
	{
		int o;
		cin >> o;

		if(o == 1)
		{
			int i, v;
			cin >> i >> v;

			if(i != 1) add(h[i], h[i-1], -1);
			if(i != N) add(h[i], h[i+1], -1);

			h[i] = v;

			if(i != 1) add(h[i], h[i-1], +1);
			if(i != N) add(h[i], h[i+1], +1);
		}
		else
		{
			int H;
			cin >> H;

			cout << get(H) << '\n';
		}
	}
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 4 ms 8576 KB Output is correct
7 Correct 4 ms 8660 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 4 ms 8576 KB Output is correct
7 Correct 4 ms 8660 KB Output is correct
8 Correct 30 ms 9804 KB Output is correct
9 Correct 57 ms 11096 KB Output is correct
10 Correct 56 ms 11192 KB Output is correct
11 Correct 27 ms 9732 KB Output is correct
12 Correct 42 ms 10836 KB Output is correct
13 Correct 46 ms 10916 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 4 ms 8532 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 4 ms 8576 KB Output is correct
7 Correct 4 ms 8660 KB Output is correct
8 Correct 30 ms 9804 KB Output is correct
9 Correct 57 ms 11096 KB Output is correct
10 Correct 56 ms 11192 KB Output is correct
11 Correct 27 ms 9732 KB Output is correct
12 Correct 42 ms 10836 KB Output is correct
13 Correct 46 ms 10916 KB Output is correct
14 Correct 87 ms 11080 KB Output is correct
15 Correct 88 ms 11028 KB Output is correct
16 Correct 95 ms 11052 KB Output is correct
17 Correct 86 ms 11088 KB Output is correct
18 Correct 92 ms 11240 KB Output is correct