Submission #204710

#	Time	Username	Problem	Language	Result	Execution time	Memory
204710		luciocf	Simple game (IZhO17_game)	C++14	100 / 100	100 ms	6904 KiB

game

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6+10;

int n, m;
int a[maxn];

int bit[maxn];

void upd(int x, int v)
{
	for (; x < maxn; x += (x&-x))
		bit[x] += v;
}

int soma(int x)
{
	int ans = 0;
	for (; x > 0; x -= (x&-x))
		ans += bit[x];
	return ans;
}

void range_upd(int l, int r, int x)
{
	upd(l, x);
	upd(r+1, -x);
}

int main(void)
{
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	for (int i = 1; i < n; i++)
	{
		if (a[i] <= a[i+1])
			range_upd(a[i], a[i+1]-1, 1);
		else
			range_upd(a[i+1]+1, a[i], 1);
	}

	for (int i = 1; i <= m; i++)
	{
		int op;
		scanf("%d", &op);

		if (op == 1)
		{
			int pos, v;
			scanf("%d %d", &pos, &v);

			if (pos != 1)
			{
				if (a[pos-1] <= a[pos])
					range_upd(a[pos-1], a[pos]-1, -1);
				else
					range_upd(a[pos]+1, a[pos-1], -1);

				if (a[pos-1] <= v)
					range_upd(a[pos-1], v-1, 1);
				else
					range_upd(v+1, a[pos-1], 1);
			}

			if (pos != n)
			{
				if (a[pos] <= a[pos+1])
					range_upd(a[pos], a[pos+1]-1, -1);
				else
					range_upd(a[pos+1]+1, a[pos], -1);

				if (v <= a[pos+1])
					range_upd(v, a[pos+1]-1, 1);
				else
					range_upd(a[pos+1]+1, v, 1);
			}

			a[pos] = v;
		}
		else
		{
			int H;
			scanf("%d", &H);

			printf("%d\n", (H == a[n] ? soma(H)+1 : soma(H)));
		}
	}
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
game.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
game.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &op);
   ~~~~~^~~~~~~~~~~
game.cpp:55:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &pos, &v);
    ~~~~~^~~~~~~~~~~~~~~~~~~
game.cpp:88:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &H);
    ~~~~~^~~~~~~~~~

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