#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef pair<int,int> pii;
const int MN = 2e5+5;
int A[MN],G[MN],T[4*MN],N,M,S;
vector<int> V;
pii Q[MN];
void upt(int s, int e, int x, int y, int val, int pos)
{
//if(s==0 && e==S) cout << x << ' ' << y << ' ' << val << '\n';
if(e<x || y<s) return;
if(x<=s && e<=y){
T[pos] += val;
return;
}
int m = (s+e)/2;
upt(s,m,x,y,val,2*pos);
upt(m+1,e,x,y,val,2*pos+1);
}
int act(int s, int e, int x, int pos)
{
if(x<s || e<x) return 0;
if(s==e) return T[pos];
int m = (s+e)/2;
return T[pos]+act(s,m,x,2*pos)+act(m+1,e,x,2*pos+1);
}
bool comb(int x)
{
return A[x]!=-1&&x<N&&x>1&&A[x]<=A[x-1]&&A[x]<A[x+1];
}
bool isol(int x)
{
return (x==1||A[x-1]==-1||A[x]>A[x-1])&&(x==N||A[x+1]==-1||A[x]>=A[x+1]);
}
void trans(int x, int val)
{
if(comb(x)) upt(0,S,0,A[x],1,1);
if(isol(x)) upt(0,S,0,A[x],-1,1);
if(x<N){
if(comb(x+1)) upt(0,S,0,A[x+1],1,1);
if(!comb(x+1)&&!isol(x+1)&&A[x+1]<=A[x]) upt(0,S,0,A[x+1],1,1);
}
if(x>1){
if(comb(x-1)) upt(0,S,0,A[x-1],1,1);
if(!comb(x-1)&&!isol(x-1)&&A[x-1]<A[x]) upt(0,S,0,A[x-1],1,1);
}
A[x] = -1;
if(x<N){
if(isol(x+1)&&A[x+1]<=val) upt(0,S,0,A[x+1],-1,1);
if(!comb(x+1)&&!isol(x+1)&&A[x+1]<=val) upt(0,S,0,A[x+1],-1,1);
}
if(x>1){
if(isol(x-1)&&A[x-1]<val) upt(0,S,0,A[x-1],-1,1);
if(!comb(x-1)&&!isol(x-1)&&A[x-1]<val) upt(0,S,0,A[x-1],-1,1);
}
A[x] = val;
if(comb(x)) upt(0,S,0,A[x],-1,1);
if(isol(x)) upt(0,S,0,A[x],1,1);
}
int main()
{
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> N >> M;
for(int i=1; i<=N; i++) cin >> G[i];
int T,B,C,D;
for(int i=0; i<M; i++){
cin >> T;
if(T==1){
cin >> B;
Q[i] = pii(B,0);
V.push_back(B);
}
if(T==2){
cin >> C >> D;
Q[i] = pii(C,D);
}
}
sort(V.begin(),V.end());
V.erase(unique(V.begin(),V.end()),V.end());
S = V.size();
int val;
for(int i=1; i<=N; i++) A[i] = -1;
//upt(0,S,0,S-1,1,1);
for(int i=1; i<=N; i++){
val = upper_bound(V.begin(),V.end(),G[i])-V.begin()-1;
//cout << val << '\n';
trans(i,val);
}
//cout << act(0,S,1,1) << '\n';
//cout << '\n';
for(int i=0; i<M; i++){
if(Q[i].vb){
Q[i].vb = val = upper_bound(V.begin(),V.end(),Q[i].vb)-V.begin()-1;
//cout << val << '\n';
trans(Q[i].va,Q[i].vb);
}
else{
Q[i].va = lower_bound(V.begin(),V.end(),Q[i].va)-V.begin();
cout << act(0,S,Q[i].va,1) << '\n';
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
504 KB |
Output is correct |
6 |
Correct |
3 ms |
420 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
4 ms |
376 KB |
Output is correct |
10 |
Correct |
4 ms |
376 KB |
Output is correct |
11 |
Correct |
4 ms |
504 KB |
Output is correct |
12 |
Correct |
4 ms |
504 KB |
Output is correct |
13 |
Correct |
4 ms |
504 KB |
Output is correct |
14 |
Correct |
4 ms |
376 KB |
Output is correct |
15 |
Correct |
4 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
4 ms |
504 KB |
Output is correct |
4 |
Correct |
21 ms |
1564 KB |
Output is correct |
5 |
Correct |
39 ms |
2168 KB |
Output is correct |
6 |
Correct |
64 ms |
3320 KB |
Output is correct |
7 |
Correct |
105 ms |
4924 KB |
Output is correct |
8 |
Correct |
127 ms |
5848 KB |
Output is correct |
9 |
Correct |
230 ms |
9960 KB |
Output is correct |
10 |
Correct |
191 ms |
7924 KB |
Output is correct |
11 |
Correct |
260 ms |
11004 KB |
Output is correct |
12 |
Correct |
293 ms |
11776 KB |
Output is correct |
13 |
Correct |
284 ms |
11908 KB |
Output is correct |
14 |
Correct |
281 ms |
11692 KB |
Output is correct |
15 |
Correct |
286 ms |
11720 KB |
Output is correct |
16 |
Correct |
291 ms |
11888 KB |
Output is correct |
17 |
Correct |
292 ms |
11836 KB |
Output is correct |
18 |
Correct |
292 ms |
11912 KB |
Output is correct |
19 |
Correct |
284 ms |
11888 KB |
Output is correct |
20 |
Correct |
297 ms |
11904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
504 KB |
Output is correct |
6 |
Correct |
3 ms |
420 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
4 ms |
376 KB |
Output is correct |
10 |
Correct |
4 ms |
376 KB |
Output is correct |
11 |
Correct |
4 ms |
504 KB |
Output is correct |
12 |
Correct |
4 ms |
504 KB |
Output is correct |
13 |
Correct |
4 ms |
504 KB |
Output is correct |
14 |
Correct |
4 ms |
376 KB |
Output is correct |
15 |
Correct |
4 ms |
504 KB |
Output is correct |
16 |
Correct |
3 ms |
504 KB |
Output is correct |
17 |
Correct |
5 ms |
504 KB |
Output is correct |
18 |
Correct |
4 ms |
504 KB |
Output is correct |
19 |
Correct |
21 ms |
1564 KB |
Output is correct |
20 |
Correct |
39 ms |
2168 KB |
Output is correct |
21 |
Correct |
64 ms |
3320 KB |
Output is correct |
22 |
Correct |
105 ms |
4924 KB |
Output is correct |
23 |
Correct |
127 ms |
5848 KB |
Output is correct |
24 |
Correct |
230 ms |
9960 KB |
Output is correct |
25 |
Correct |
191 ms |
7924 KB |
Output is correct |
26 |
Correct |
260 ms |
11004 KB |
Output is correct |
27 |
Correct |
293 ms |
11776 KB |
Output is correct |
28 |
Correct |
284 ms |
11908 KB |
Output is correct |
29 |
Correct |
281 ms |
11692 KB |
Output is correct |
30 |
Correct |
286 ms |
11720 KB |
Output is correct |
31 |
Correct |
291 ms |
11888 KB |
Output is correct |
32 |
Correct |
292 ms |
11836 KB |
Output is correct |
33 |
Correct |
292 ms |
11912 KB |
Output is correct |
34 |
Correct |
284 ms |
11888 KB |
Output is correct |
35 |
Correct |
297 ms |
11904 KB |
Output is correct |
36 |
Correct |
4 ms |
504 KB |
Output is correct |
37 |
Correct |
5 ms |
504 KB |
Output is correct |
38 |
Correct |
5 ms |
504 KB |
Output is correct |
39 |
Correct |
22 ms |
1144 KB |
Output is correct |
40 |
Correct |
42 ms |
2040 KB |
Output is correct |
41 |
Correct |
72 ms |
2936 KB |
Output is correct |
42 |
Correct |
102 ms |
4216 KB |
Output is correct |
43 |
Correct |
141 ms |
5156 KB |
Output is correct |
44 |
Correct |
256 ms |
8972 KB |
Output is correct |
45 |
Correct |
207 ms |
7032 KB |
Output is correct |
46 |
Correct |
231 ms |
8372 KB |
Output is correct |
47 |
Correct |
315 ms |
10212 KB |
Output is correct |
48 |
Correct |
342 ms |
10424 KB |
Output is correct |
49 |
Correct |
323 ms |
10532 KB |
Output is correct |
50 |
Correct |
312 ms |
10228 KB |
Output is correct |
51 |
Correct |
340 ms |
10696 KB |
Output is correct |
52 |
Correct |
322 ms |
10492 KB |
Output is correct |
53 |
Correct |
341 ms |
10584 KB |
Output is correct |
54 |
Correct |
355 ms |
10480 KB |
Output is correct |
55 |
Correct |
346 ms |
10740 KB |
Output is correct |