Submission #52393

#	Time	Username	Problem	Language	Result	Execution time	Memory
52393		MatheusLealV	Simple game (IZhO17_game)	C++17	100 / 100	147 ms	26584 KiB

game

#include <bits/stdc++.h>
#define N 1000050
using namespace std;

int bit[N], n, q, v[N], qtd[N];

void upd(int x, int v)
{
	x += 2;

	for(int i = x; i < N; i += (i&-i)) bit[i] += v;
}

int query(int x)
{
	int sum = 0;

	x += 2;

	for(int i = x; i > 0; i -= (i&-i)) sum += bit[i];

	return sum;
}

void remove(int i)
{
	if(i > 1)
	{
		int A = min(v[i], v[i - 1]), B = max(v[i], v[i - 1]);

		A ++, B --;

		if(A <= B)
		{
			upd(A, -1);

			upd(B + 1, +1);
		}
	}

	if(i < n)
	{
		int A = min(v[i], v[i + 1]), B = max(v[i], v[i + 1]);

		A ++, B --;

		if(A <= B)
		{
			upd(A, -1);

			upd(B + 1, +1);
		}
	}
}

void add(int i, int h)
{
	v[i] = h;

	if(i > 1)
	{
		int A = min(v[i], v[i - 1]), B = max(v[i], v[i - 1]);

		A ++, B--;

		if(A <= B)
		{
			upd(A, +1);

			upd(B + 1, -1);
		}
	}

	if(i < n)
	{
		int A = min(v[i], v[i + 1]), B = max(v[i], v[i + 1]);

		A ++, B --;

		if(A <= B)
		{
			upd(A, +1);

			upd(B + 1, -1);
		}
	}	
}

void Update(int i, int h)
{
	qtd[v[i]] --, qtd[h] ++;

	remove(i);

	add(i, h);
}

int Query(int H)
{
	return query(H) + qtd[H];
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>q;

	for(int i = 1; i <= n; i++)
	{
		cin>>v[i];

		qtd[v[i]] ++;
	}

	for(int i = 1; i <= n; i++)
	{
		if(i > 1)
		{
			int A = min(v[i], v[i - 1]), B = max(v[i], v[i - 1]);

			A ++, B --;

			if(A > B) continue;

			upd(A, +1);

			upd(B + 1, -1);
		}
	}

	for(int i = 0; i < q; i++)
	{
		int t, a, b;

		cin>>t>>a;

		if(t == 2) cout<<Query(a)<<"\n";

		else cin>>b, Update(a, b);
	}
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51