oj.uz

Submission #52391

# Submission time Handle Problem Language Result Execution time Memory
52391 2018-06-25T17:46:56 Z MatheusLealV Simple game (IZhO17_game) C++17
0 / 100
 10 ms 6500 KB 
#include <bits/stdc++.h>
#define N 100050
using namespace std;

int bit[N], n, q, v[N], qtd[10*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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 10 ms 6500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 10 ms 6500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 10 ms 6500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -