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>
using namespace std;
int aib[1000005];
int v[1000005];
int n, q;
void update(int poz, int val)
{
for(int i = poz; i <= 1000000; i += (i & (-i)))
aib[i] += val;
return;
}
int query(int poz)
{
int sum = 0;
for(int i = poz; i >= 1; i -= (i & (-i)))
sum += aib[i];
return sum;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n>>q;
for(int i = 1; i <= n; i++)
cin>>v[i];
for(int i = 2; i <= n; i++)
{
int sus = max(v[i], v[i - 1]);
int jos = min(v[i], v[i - 1]);
update(jos, 1);
update(sus, -1);
}
for(int i = 1; i <= q; i++)
{
int tip;
cin>>tip;
if(tip == 1)
{
int a, b;
cin>>a>>b;
if(a > 1)
{
int st = a - 1;
int sus = max(v[st], v[a]), jos = min(v[st], v[a]);
update(sus, 1);
update(jos, -1);
sus = max(v[st], b);
jos = min(v[st], b);
update(sus, -1);
update(jos, 1);
}
if(a < n)
{
int st = a + 1;
int sus = max(v[st], v[a]), jos = min(v[st], v[a]);
update(sus, 1);
update(jos, -1);
sus = max(v[st], b);
jos = min(v[st], b);
update(sus, -1);
update(jos, 1);
}
v[a] = b;
}
else
{
int a;
cin>>a;
cout<<query(a)<<'\n';
}
}
return 0;
}
/*
3 3
1 5 1
2 3
1 1 5
2 3
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |