#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int h[100005], tree[4000005] = {0}, lazy[4000000] = {0};
int getSumUtil(int ss, int se, int qs, int qe, int si);
int getSum(int q);
void updateRangeUtil(int si, int ss, int se, int us, int ue, int diff);
void updateRange(int us, int ue, int diff);
int Ans(int l, int m, int r, int H);
int RealAns(int n, int H)
{
int ans=0;
char curState='0';
for (int i=0; i<n; i++)
if (h[i]<H)
{
if (curState=='>')
ans++;
curState='<';
}
else
{
if (curState=='<')
ans++;
curState='>';
}
return ans;
}
int main()
{
int n, m;
cin>>n>>m;
for (int i=0; i<n; i++)
scanf("%d", h+i);
for (int i=1; i<n; i++)
{
updateRange(min(h[i-1], h[i]), max(h[i-1], h[i]), 1);
if (i!=n-1) updateRange(h[i], h[i], -1);
}
/*
cout<<"\n\n";
for (int H=1; H<=15; H++)
cout<<H<<": "<<getSum(H)<<'\n';
*/
while (m--)
{
int type;
cin>>type;
if (type==1)
{
int i, H;
cin>>i>>H; i--;
int l_h=(i?h[i-1]:-1), r_h=(i+1<n?h[i+1]:-1);
updateRange(min(l_h, h[i]), max(l_h, h[i]), -1);
updateRange(min(h[i], r_h), max(h[i], r_h), -1);
updateRange(h[i], h[i], 1);
updateRange(min(l_h, H), max(l_h, H), 1);
updateRange(min(H, r_h), max(H, r_h), 1);
updateRange(H, H, -1);
/*
updateRange(min(h[i], H)+1, max(h[i], H)-1,
Ans(l_h, H, r_h, min(h[i], H)+1)-Ans(l_h, h[i], r_h, min(h[i], H)+1));
updateRange(h[i], h[i], Ans(l_h, H, r_h, h[i])-Ans(l_h, h[i], r_h, h[i]));
updateRange(H, H, Ans(l_h, H, r_h, H)-Ans(l_h, h[i], r_h, H));
*/
h[i]=H;
/*
for (int H=1; H<=5; H++)
cout<<H<<": "<<getSum(H)<<'\n';
*/
}
else
{
int H;
cin>>H;
/*
cout<<"\t\t"<<getSum(H)<<".\n";
cout<<"Real ans = \t"<<RealAns(n, H)<<".\n";
*/
cout<<getSum(H)<<'\n';
}
}
char I;
cin >> I;
return 0;
}
/*
9 1000000
2 5 3 8 1 10 8 15 5
*/
int Ans(int l, int m, int r, int H)
{
int ans=0;
if (l!=-1 && H>=min(l, m) && H<=max(l, m)) ans++;
if (r!=-1 && H>=min(m, r) && H<=max(m, r)) ans++;
if (H==m) ans--;
return ans;
}
int getSumUtil(int ss, int se, int qs, int qe, int si)
{
if (lazy[si] != 0)
{
tree[si] += (se-ss+1)*lazy[si];
if (ss != se)
{
lazy[si*2+1] += lazy[si];
lazy[si*2+2] += lazy[si];
}
lazy[si] = 0;
}
if (ss>se || ss>qe || se<qs)
return 0;
if (ss>=qs && se<=qe)
return tree[si];
int mid = (ss + se)/2;
return getSumUtil(ss, mid, qs, qe, 2*si+1) +
getSumUtil(mid+1, se, qs, qe, 2*si+2);
}
int getSum(int q)
{
// q>=0 && q<n
int n=1000001;
return getSumUtil(0, n-1, q-1, q-1, 0);
}
void updateRangeUtil(int si, int ss, int se, int us, int ue, int diff)
{
if (lazy[si] != 0)
{
tree[si] += (se-ss+1)*lazy[si];
if (ss != se)
{
lazy[si*2 + 1] += lazy[si];
lazy[si*2 + 2] += lazy[si];
}
lazy[si] = 0;
}
if (ss>se || ss>ue || se<us)
return ;
if (ss>=us && se<=ue)
{
tree[si] += (se-ss+1)*diff;
if (ss != se)
{
lazy[si*2 + 1] += diff;
lazy[si*2 + 2] += diff;
}
return;
}
int mid = (ss+se)/2;
updateRangeUtil(si*2+1, ss, mid, us, ue, diff);
updateRangeUtil(si*2+2, mid+1, se, us, ue, diff);
tree[si] = tree[si*2+1] + tree[si*2+2];
}
void updateRange(int us, int ue, int diff)
{
if (us>ue) return;
int n=1000001;
updateRangeUtil(0, 0, n-1, us-1, ue-1, diff);
}
Compilation message
game.cpp: In function 'int main()':
game.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", h+i);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
