This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define ft first
#define sc second
using namespace std;
const int mod=1e9+7,INF=1e17;
const int N = 1e6 + 5;
int d[4 * N];
int a[N];
void add(int l,int r,int v, int x, int lx,int rx){
if(l>=rx || lx>=r){
return;
}
if(lx>=l && rx<=r){
d[x]+=v;
return;
}
int m=(lx+rx)/2;
add(l,r,v,x*2+1,lx,m);
add(l,r,v,x*2+2,m,rx);
}
void del(int l,int r,int v, int x, int lx,int rx){
if(l>=rx || lx>=r){
return;
}
if(lx>=l && rx<=r){
d[x]-=v;
return;
}
int m=(lx+rx)/2;
del(l,r,v,x*2+1,lx,m);
del(l,r,v,x*2+2,m,rx);
}
long long get(int i,int x,int lx,int rx){
if(rx-lx==1){
return d[x];
}
int m=(lx+rx)/2;
if(i<m){
return get(i,x*2+1,lx,m)+d[x];
}
else{
return get(i,x*2+2,m,rx)+d[x];
}
}
main(){
int n,m;
cin >> n >> m;
for(int i=0;i<n;i++){
cin >> a[i];
if(i==0){
continue;
}
int l=min(a[i-1],a[i]);
int r=max(a[i-1],a[i]);
add(l,r,1,0,0,N);
}
for(int i=0;i<m;i++){
int type;
cin >> type;
if(type==1){
int pos,val;
cin >> pos >> val;
pos--;
if(pos>0){
int l1=min(a[pos-1],a[pos]);
int r1=max(a[pos-1],a[pos]);
del(l1,r1,1,0,0,N);
}
if(pos<n-1){
int l1=min(a[pos+1],a[pos]);
int r1=max(a[pos+1],a[pos]);
del(l1,r1,1,0,0,N);
}
a[pos]=val;
if(pos>0){
int l1=min(a[pos-1],a[pos]);
int r1=max(a[pos-1],a[pos]);
add(l1,r1,1,0,0,N);
}
if(pos<n-1){
int l1=min(a[pos+1],a[pos]);
int r1=max(a[pos+1],a[pos]);
add(l1,r1,1,0,0,N);
}
}
else{
long long k;
cin >> k;
k--;
cout << get(k,0,0,N) << endl;
}
}
}
Compilation message (stderr)
game.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
50 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |