#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
using namespace std;
using ll=long long;
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
const int N=400010,MOD=1e9+7,M=1<<19;
const char en='\n';
const ll LLINF=1ll<<60;
int n,q,h[N],ti[N],a[N],b[N],seg[M*2+10];
void upd(int i,int x)
{
for (i+=M;i;i/=2) seg[i]+=x;
}
int ge(int l,int r,int lo=0,int hi=M,int i=1)
{
if (lo>=l && hi<=r) return seg[i];
if (lo>=r || hi<=l) return 0;
int mid=(lo+hi)/2;
return ge(l,r,lo,mid,i*2)+ge(l,r,mid,hi,i*2+1);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>q;
set<int> s;
for (int i=0;i<n;++i) cin>>h[i],s.insert(h[i]);
for (int i=0;i<q;++i)
{
cin>>ti[i];
if (ti[i]==1)
{
cin>>a[i];
s.insert(a[i]);
}
else
{
cin>>a[i]>>b[i];
s.insert(b[i]);
}
}
vi v(all(s));
for (int i=0;i<n;++i) h[i]=lower_bound(all(v),h[i])-v.begin();
for (int i=0;i<q;++i)
{
if (ti[i]==1) a[i]=lower_bound(all(v),a[i])-v.begin();
else b[i]=lower_bound(all(v),b[i])-v.begin();
}
for (int i=0;i<n;++i)
{
upd(h[i],1);
if (i) upd(min(h[i],h[i-1]),-1);
}
for (int i=0;i<q;++i)
{
if (ti[i]==1)
{
cout<<ge(a[i],M)<<en;
}
else
{
--a[i];
upd(h[a[i]],-1);
if (a[i]) upd(min(h[a[i]],h[a[i]-1]),1);
if (a[i]<n-1) upd(min(h[a[i]],h[a[i]+1]),1);
h[a[i]]=b[i];
upd(h[a[i]],1);
if (a[i]) upd(min(h[a[i]],h[a[i]-1]),-1);
if (a[i]<n-1) upd(min(h[a[i]],h[a[i]+1]),-1);
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
588 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
588 KB |
Output is correct |
10 |
Correct |
2 ms |
588 KB |
Output is correct |
11 |
Correct |
2 ms |
680 KB |
Output is correct |
12 |
Correct |
3 ms |
588 KB |
Output is correct |
13 |
Correct |
3 ms |
588 KB |
Output is correct |
14 |
Correct |
3 ms |
588 KB |
Output is correct |
15 |
Correct |
3 ms |
588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
588 KB |
Output is correct |
3 |
Correct |
3 ms |
716 KB |
Output is correct |
4 |
Correct |
22 ms |
2828 KB |
Output is correct |
5 |
Correct |
45 ms |
5208 KB |
Output is correct |
6 |
Correct |
83 ms |
7920 KB |
Output is correct |
7 |
Correct |
131 ms |
11936 KB |
Output is correct |
8 |
Correct |
181 ms |
14880 KB |
Output is correct |
9 |
Correct |
441 ms |
24380 KB |
Output is correct |
10 |
Correct |
329 ms |
22572 KB |
Output is correct |
11 |
Correct |
468 ms |
28040 KB |
Output is correct |
12 |
Correct |
535 ms |
31016 KB |
Output is correct |
13 |
Correct |
524 ms |
31276 KB |
Output is correct |
14 |
Correct |
542 ms |
30696 KB |
Output is correct |
15 |
Correct |
575 ms |
30772 KB |
Output is correct |
16 |
Correct |
575 ms |
31588 KB |
Output is correct |
17 |
Correct |
532 ms |
31588 KB |
Output is correct |
18 |
Correct |
542 ms |
31564 KB |
Output is correct |
19 |
Correct |
546 ms |
31588 KB |
Output is correct |
20 |
Correct |
529 ms |
31628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
588 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
588 KB |
Output is correct |
10 |
Correct |
2 ms |
588 KB |
Output is correct |
11 |
Correct |
2 ms |
680 KB |
Output is correct |
12 |
Correct |
3 ms |
588 KB |
Output is correct |
13 |
Correct |
3 ms |
588 KB |
Output is correct |
14 |
Correct |
3 ms |
588 KB |
Output is correct |
15 |
Correct |
3 ms |
588 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
4 ms |
588 KB |
Output is correct |
18 |
Correct |
3 ms |
716 KB |
Output is correct |
19 |
Correct |
22 ms |
2828 KB |
Output is correct |
20 |
Correct |
45 ms |
5208 KB |
Output is correct |
21 |
Correct |
83 ms |
7920 KB |
Output is correct |
22 |
Correct |
131 ms |
11936 KB |
Output is correct |
23 |
Correct |
181 ms |
14880 KB |
Output is correct |
24 |
Correct |
441 ms |
24380 KB |
Output is correct |
25 |
Correct |
329 ms |
22572 KB |
Output is correct |
26 |
Correct |
468 ms |
28040 KB |
Output is correct |
27 |
Correct |
535 ms |
31016 KB |
Output is correct |
28 |
Correct |
524 ms |
31276 KB |
Output is correct |
29 |
Correct |
542 ms |
30696 KB |
Output is correct |
30 |
Correct |
575 ms |
30772 KB |
Output is correct |
31 |
Correct |
575 ms |
31588 KB |
Output is correct |
32 |
Correct |
532 ms |
31588 KB |
Output is correct |
33 |
Correct |
542 ms |
31564 KB |
Output is correct |
34 |
Correct |
546 ms |
31588 KB |
Output is correct |
35 |
Correct |
529 ms |
31628 KB |
Output is correct |
36 |
Correct |
2 ms |
460 KB |
Output is correct |
37 |
Correct |
3 ms |
588 KB |
Output is correct |
38 |
Correct |
5 ms |
716 KB |
Output is correct |
39 |
Correct |
20 ms |
2904 KB |
Output is correct |
40 |
Correct |
39 ms |
4888 KB |
Output is correct |
41 |
Correct |
80 ms |
7960 KB |
Output is correct |
42 |
Correct |
111 ms |
11360 KB |
Output is correct |
43 |
Correct |
203 ms |
15024 KB |
Output is correct |
44 |
Correct |
416 ms |
26948 KB |
Output is correct |
45 |
Correct |
306 ms |
22000 KB |
Output is correct |
46 |
Correct |
342 ms |
24372 KB |
Output is correct |
47 |
Correct |
501 ms |
31576 KB |
Output is correct |
48 |
Correct |
536 ms |
31972 KB |
Output is correct |
49 |
Correct |
542 ms |
31908 KB |
Output is correct |
50 |
Correct |
472 ms |
31528 KB |
Output is correct |
51 |
Correct |
502 ms |
32412 KB |
Output is correct |
52 |
Correct |
480 ms |
32356 KB |
Output is correct |
53 |
Correct |
489 ms |
32404 KB |
Output is correct |
54 |
Correct |
494 ms |
32400 KB |
Output is correct |
55 |
Correct |
519 ms |
32480 KB |
Output is correct |