#include <bits/stdc++.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;
int a[100001];
int lazy[4000001],value[4000001];
void update(int id,int l,int r,int L,int R,int d){
if(L>R) return;
value[id]+=lazy[id];
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
lazy[id]=0;
if(l>R || L>r){
return;
}
if(L<=l && r<=R){
value[id]+=d;
lazy[id*2]+=d;
lazy[id*2+1]+=d;
return;
}
int m=l+r>>1;
update(id*2,l,m,L,R,d);
update(id*2+1,m+1,r,L,R,d);
value[id]=value[id*2]+value[id*2+1];
}
int query(int id,int l,int r,int L,int R){
value[id]+=lazy[id];
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
lazy[id]=0;
if(l>R || L>r){
return 0;
}
if(L<=l && r<=R){
return value[id];
}
int m=l+r>>1;
return query(id*2,l,m,L,R)+query(id*2+1,m+1,r,L,R);
}
int main() {
//ios_base::sync_with_stdio(NULL);
// cin.tie(NULL);
// cout.tie(NULL);
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i];
}
for(int i=1;i<n;i++){
update(1,1,1000000,min(a[i],a[i+1]),max(a[i],a[i+1]),1);
}
for(int i=1;i<=m;i++){
int type;
cin >> type;
if(type==1){
int pos,val;
cin >> pos >> val;
if(pos!=1){
update(1,1,1000000,min(a[pos-1],a[pos]),max(a[pos-1],a[pos]),-1);
update(1,1,1000000,min(a[pos-1],val),max(a[pos-1],val),1);
}
if(pos!=n){
update(1,1,1000000,min(a[pos],a[pos+1]),max(a[pos],a[pos+1]),-1);
update(1,1,1000000,min(a[pos+1],val),max(a[pos+1],val),1);
}
a[pos]=val;
}
else{
int h;
cin >> h;
cout << query(1,1,1000000,h,h) << '\n';
}
}
}
Compilation message
game.cpp: In function 'void update(int, int, int, int, int, int)':
game.cpp:22:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | int m=l+r>>1;
| ~^~
game.cpp: In function 'int query(int, int, int, int, int)':
game.cpp:38:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int m=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Runtime error |
15 ms |
8300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Runtime error |
15 ms |
8300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Runtime error |
15 ms |
8300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
