Submission #536684

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
536684	2022-03-13T20:31:05 Z	blue	Simple game (IZhO17_game)	C++17	100 / 100	95 ms	11240 KB

game

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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