oj.uz

Submission #52393

# Submission time Handle Problem Language Result Execution time Memory
52393 2018-06-25T17:47:49 Z MatheusLealV Simple game (IZhO17_game) C++17
100 / 100
 147 ms 26584 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 7268 KB Output is correct
3 Correct 11 ms 7308 KB Output is correct
4 Correct 8 ms 7316 KB Output is correct
5 Correct 9 ms 7352 KB Output is correct
6 Correct 8 ms 7608 KB Output is correct
7 Correct 4 ms 7608 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 8 ms 7268 KB Output is correct
3 Correct 11 ms 7308 KB Output is correct
4 Correct 8 ms 7316 KB Output is correct
5 Correct 9 ms 7352 KB Output is correct
6 Correct 8 ms 7608 KB Output is correct
7 Correct 4 ms 7608 KB Output is correct
8 Correct 43 ms 7608 KB Output is correct
9 Correct 88 ms 12064 KB Output is correct
10 Correct 82 ms 13588 KB Output is correct
11 Correct 36 ms 13588 KB Output is correct
12 Correct 49 ms 13588 KB Output is correct
13 Correct 54 ms 13588 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 8 ms 7268 KB Output is correct
3 Correct 11 ms 7308 KB Output is correct
4 Correct 8 ms 7316 KB Output is correct
5 Correct 9 ms 7352 KB Output is correct
6 Correct 8 ms 7608 KB Output is correct
7 Correct 4 ms 7608 KB Output is correct
8 Correct 43 ms 7608 KB Output is correct
9 Correct 88 ms 12064 KB Output is correct
10 Correct 82 ms 13588 KB Output is correct
11 Correct 36 ms 13588 KB Output is correct
12 Correct 49 ms 13588 KB Output is correct
13 Correct 54 ms 13588 KB Output is correct
14 Correct 126 ms 18804 KB Output is correct
15 Correct 119 ms 20732 KB Output is correct
16 Correct 147 ms 22676 KB Output is correct
17 Correct 107 ms 24604 KB Output is correct
18 Correct 133 ms 26584 KB Output is correct