#include <bits/stdc++.h>
using namespace std;
int bit[1000010];
int h[100010];
void update(int i, int x) {
for(int j=i; j<=1000010; j+=j&-j){
bit[j] += x;
}
}
int query(int i) {
int soma = 0;
for(int j = i; j>0; j-=j&-j) {
soma+=bit[j];
}
return soma;
}
int main()
{
int n, m; scanf("%d %d", &n, &m);
scanf("%d", &h[1]);
for(int i=2;i<=n;i++){
scanf("%d", &h[i]);
update(min(h[i-1], h[i]), 1);
update(max(h[i-1], h[i])+1, -1);
}
for(int i=0;i<m;i++){
int t; scanf("%d", &t);
if(t==2){
int hq; scanf("%d", &hq);
printf("%d\n", query(hq));
}else if(t==1){
int pos, val; scanf("%d %d", &pos, &val);
if(pos==1){
//elimina a chain com o vertice seguinte
update(min(h[pos], h[pos+1]), -1);
update(max(h[pos], h[pos+1])+1, 1);
//cria a chain(com a nova altura) com o vertice seguinte
update(min(val, h[pos+1]), 1);
update(max(val, h[pos+1])+1, -1);
}else if(pos==n){
//elimina a chain com o vertice anterior
update(min(h[pos], h[pos-1]), -1);
update(max(h[pos], h[pos-1])+1, 1);
//cria a chain(com a nova altura) com o vertice anterior
update(min(val, h[pos-1]), 1);
update(max(val, h[pos-1])+1, -1);
}else{
//elimina a chain com o vertice seguinte
update(min(h[pos], h[pos+1]), -1);
update(max(h[pos], h[pos+1])+1, 1);
//elimina a chain com o vertice anterior
update(min(h[pos], h[pos-1]), -1);
update(max(h[pos], h[pos-1])+1, 1);
//cria a chain(com a nova altura) com o vertice seguinte
update(min(val, h[pos+1]), 1);
update(max(val, h[pos+1])+1, -1);
//cria a chain(com a nova altura) com o vertice anterior
update(min(val, h[pos-1]), 1);
update(max(val, h[pos-1])+1, -1);
}
h[pos] = val;
}
}
return 0;
}
Compilation message
game.cpp: In function 'int main()':
game.cpp:24:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | int n, m; scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
game.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | scanf("%d", &h[1]);
| ~~~~~^~~~~~~~~~~~~
game.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | scanf("%d", &h[i]);
| ~~~~~^~~~~~~~~~~~~
game.cpp:32:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | int t; scanf("%d", &t);
| ~~~~~^~~~~~~~~~
game.cpp:34:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | int hq; scanf("%d", &hq);
| ~~~~~^~~~~~~~~~~
game.cpp:37:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | int pos, val; scanf("%d %d", &pos, &val);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
4052 KB |
Output is correct |
3 |
Correct |
3 ms |
4032 KB |
Output is correct |
4 |
Correct |
3 ms |
4052 KB |
Output is correct |
5 |
Correct |
2 ms |
4052 KB |
Output is correct |
6 |
Correct |
2 ms |
4052 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
4052 KB |
Output is correct |
3 |
Correct |
3 ms |
4032 KB |
Output is correct |
4 |
Correct |
3 ms |
4052 KB |
Output is correct |
5 |
Correct |
2 ms |
4052 KB |
Output is correct |
6 |
Correct |
2 ms |
4052 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
40 ms |
1676 KB |
Output is correct |
9 |
Correct |
48 ms |
6732 KB |
Output is correct |
10 |
Correct |
49 ms |
6744 KB |
Output is correct |
11 |
Correct |
44 ms |
1528 KB |
Output is correct |
12 |
Correct |
44 ms |
2832 KB |
Output is correct |
13 |
Correct |
43 ms |
2708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
4052 KB |
Output is correct |
3 |
Correct |
3 ms |
4032 KB |
Output is correct |
4 |
Correct |
3 ms |
4052 KB |
Output is correct |
5 |
Correct |
2 ms |
4052 KB |
Output is correct |
6 |
Correct |
2 ms |
4052 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
40 ms |
1676 KB |
Output is correct |
9 |
Correct |
48 ms |
6732 KB |
Output is correct |
10 |
Correct |
49 ms |
6744 KB |
Output is correct |
11 |
Correct |
44 ms |
1528 KB |
Output is correct |
12 |
Correct |
44 ms |
2832 KB |
Output is correct |
13 |
Correct |
43 ms |
2708 KB |
Output is correct |
14 |
Correct |
60 ms |
6760 KB |
Output is correct |
15 |
Correct |
61 ms |
6740 KB |
Output is correct |
16 |
Correct |
75 ms |
6808 KB |
Output is correct |
17 |
Correct |
59 ms |
6772 KB |
Output is correct |
18 |
Correct |
58 ms |
6704 KB |
Output is correct |