oj.uz

Submission #142891

# Submission time Handle Problem Language Result Execution time Memory
142891 2019-08-12T01:52:36 Z Lawliet Simple game (IZhO17_game) C++14
100 / 100
 96 ms 7032 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 7 ms 4216 KB Output is correct
4 Correct 6 ms 4216 KB Output is correct
5 Correct 6 ms 4216 KB Output is correct
6 Correct 6 ms 4216 KB Output is correct
7 Correct 6 ms 4216 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 7 ms 4216 KB Output is correct
4 Correct 6 ms 4216 KB Output is correct
5 Correct 6 ms 4216 KB Output is correct
6 Correct 6 ms 4216 KB Output is correct
7 Correct 6 ms 4216 KB Output is correct
8 Correct 47 ms 5672 KB Output is correct
9 Correct 71 ms 6892 KB Output is correct
10 Correct 70 ms 6904 KB Output is correct
11 Correct 43 ms 5496 KB Output is correct
12 Correct 58 ms 6648 KB Output is correct
13 Correct 61 ms 6732 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 7 ms 4216 KB Output is correct
4 Correct 6 ms 4216 KB Output is correct
5 Correct 6 ms 4216 KB Output is correct
6 Correct 6 ms 4216 KB Output is correct
7 Correct 6 ms 4216 KB Output is correct
8 Correct 47 ms 5672 KB Output is correct
9 Correct 71 ms 6892 KB Output is correct
10 Correct 70 ms 6904 KB Output is correct
11 Correct 43 ms 5496 KB Output is correct
12 Correct 58 ms 6648 KB Output is correct
13 Correct 61 ms 6732 KB Output is correct
14 Correct 94 ms 6832 KB Output is correct
15 Correct 96 ms 6892 KB Output is correct
16 Correct 92 ms 7032 KB Output is correct
17 Correct 95 ms 6912 KB Output is correct
18 Correct 90 ms 6908 KB Output is correct