Submission #142891

#	Time	Username	Problem	Language	Result	Execution time	Memory
142891		Lawliet	Simple game (IZhO17_game)	C++14	100 / 100	96 ms	7032 KiB

game

#include <bits/stdc++.h>

#define MAX 1000010

using namespace std;

class FenwickTree
{
	public:
		
		void update(int i, int v)
		{
			for( ; i > 0 ; i -= i&-i)
				BIT[ i ] += v;
		}

		void sumInterval(int l, int r, int v)
		{
			update(r , v);
			if(l > 0) update(l - 1 , -v);
		}
		
		int query(int i)
		{
			int ans = 0;

			for( ; i < MAX ; i += i & -i)
				ans += BIT[ i ];

			return ans;
		}

		FenwickTree() { memset(BIT , 0 , sizeof(BIT)); }
		
	private:
		
		int BIT[MAX];
};

int n, m;
int n1, n2, n3;

int v[MAX];

FenwickTree BIT;

void update(int i, int k)
{
	if(2 <= i && i <= n) 
		BIT.sumInterval(min(v[ i ] , v[i - 1]) , max(v[i] , v[i - 1]) , k);
}

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

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

	for(int g = 1 ; g <= n ; g++)
		update(g , 1);

	for(int g = 0 ; g < m ; g++)
	{
		scanf("%d %d",&n1,&n2);

		if(n1 == 1)
		{
			scanf("%d",&n3);

			update(n2 , -1);
			update(n2 + 1 , -1);

			v[ n2 ] = n3;

			update(n2 , 1);
			update(n2 + 1 , 1);
		}
		else printf("%d\n",BIT.query( n2 ));
	}
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:55: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:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v[g]);
   ~~~~~^~~~~~~~~~~~
game.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n1,&n2);
   ~~~~~^~~~~~~~~~~~~~~~~
game.cpp:69:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&n3);
    ~~~~~^~~~~~~~~~

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