Submission #92558

#	Time	Username	Problem	Language	Result	Execution time	Memory
92558		Nodir_Bobiev	Simple game (IZhO17_game)	C++14	100 / 100	192 ms	5400 KiB

game

# include <iostream>
# include <cstdio>

using namespace std;

const int N = 1e5 + 100;
const int M = 1e6;

int n, m, t;
int h[N];
int d[M + 1];

void update(int x, int s)
{
	while(x <= M){
		d[x] += s;
		x += (x & -x);
	}
}

int get(int x){
	int s = 0;
	while(x > 0){
		s += d[x];
		x -= (x & -x);
	}
	return s;
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", h + i);
	
	for (int i = 1; i < n; i++){
		int l, r;
		l = min(h[i], h[i + 1]);
		r = max(h[i], h[i + 1]);
		update(l, +1);
		update(r + 1, -1);
	}
	
	while(m--){
		int pos, val, l, r, H;
		scanf("%d", &t);
		if(t == 1){
			scanf("%d %d", &pos, &val);
			if(pos != 1){
				
				l = min(h[pos], h[pos - 1]);
				r = max(h[pos], h[pos - 1]);
				update(l, -1); update(r + 1, +1);
				
				l = min(val, h[pos - 1]);
				r = max(val, h[pos - 1]);
				update(l, +1); update(r + 1, -1);
			}
			if(pos != n){
				
				l = min(h[pos], h[pos + 1]);
				r = max(h[pos], h[pos + 1]);
				update(l, -1); update(r + 1, +1);
				
				l = min(val, h[pos + 1]);
				r = max(val, h[pos + 1]);
				update(l, +1); update(r + 1, -1);
			}
			
			h[pos] = val;
		}
		else{
			scanf("%d", &H);
			cout << get(H) << endl;
		}
	}
}
/*

3 3
1 5 1
2 3
1 1 5
2 3

*/

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:32: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:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", h + i);
   ~~~~~^~~~~~~~~~~~~
game.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
game.cpp:48:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &pos, &val);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~
game.cpp:73: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