#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,st[4*maxN];
void update(ll pos,ll val,ll id=1,ll l=1,ll r=n)
{
if(l==r)
{
st[id]=val;
return;
}
ll mid=l+r>>1;
if(pos<=mid)update(pos,val,id*2,l,mid);
else update(pos,val,id*2+1,mid+1,r);
st[id]=max(st[id*2],st[id*2+1]);
}
ll bs1(ll i,ll val,ll id=1,ll l=1,ll r=n)
{
if(r<i||st[id]<val) return r+1;
if(l==r) return l;
ll mid=l+r>>1;
ll cc=bs1(i,val,id*2,l,mid);
if(cc==mid+1) return bs1(i,val,id*2+1,mid+1,r);
else return cc;
}
ll bs2(ll i,ll val,ll id=1,ll l=1,ll r=n)
{
if(l>i||st[id]<val) return l-1;
if(l==r) return l;
ll mid=l+r>>1;
ll cc=bs2(i,val,id*2+1,mid+1,r);
if(cc==mid) return bs2(i,val,id*2,l,mid);
else return cc;
}
ll get(ll i,ll j,ll id=1,ll l=1,ll r=n)
{
if(r<i||j<l) return -inf;
if(i<=l&&r<=j) return st[id];
ll mid=l+r>>1;
return max(get(i,j,id*2,l,mid),get(i,j,id*2+1,mid+1,r));
}
ll x;
ll a[maxN];
vector<pli>vec;
bool in[maxN];
ll q;
void solve()
{
cin >> n;
cin >> x;
for(int i=1;i<=n;i++) cin >> a[i],a[i]*=(ll)1e9,vec.pb({a[i],i}),in[i]=false,update(i,a[i]);
sort(vec.begin(),vec.end(),greater<pli>());
while(vec.size()>10) vec.pop_back();
for(int i=0;i<vec.size();i++) in[vec[i].se]=true;
cin >> q;
for(int i=1;i<=q;i++)
{
char t;
cin >> t;
if(t=='F')
{
ll id;
cin >> id;
ll ans=1;
if(x==id) cout << 0 <<'\n';
else if(id<x)
{
ans+=x-id-1;
ll cc=get(id,x-1);
ll pos2=bs1(x+1,cc);
ans+=pos2-x-1;
cout << ans << '\n';
}
else
{
ans+=id-x-1;
ll cc=get(x+1,id);
ll pos2=bs2(x-1,cc);
ans+=x-pos2-1;
cout << ans << '\n';
}
}
else
{
ll id,p;
cin >> id >> p;
ll newval=vec[p-1].fi+1;
a[id]=newval;
update(id,a[id]);
vec[p-1].fi++;
for(int j=p-2;j>=0;j--)
{
if(vec[j].fi==vec[j+1].fi)
{
vec[j].fi++;
a[vec[j].se]++;
update(vec[j].se,a[vec[j].se]);
}
}
vec[p-1].fi--;
if(in[id])
{
for(int i=0;i<vec.size();i++) if(vec[i].se==id) vec[i].fi=newval;
}
else
{
vec.pb({newval,id});
}
in[id]=true;
sort(vec.begin(),vec.end(),greater<pli>());
while(vec.size()>10)
{
in[vec.back().se]=false;
vec.pop_back();
}
}
}
//for(int i=1;i<=n;i++) cout << a[i] <<' ';
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
Compilation message
cake.cpp: In function 'void update(ll, ll, ll, ll, ll)':
cake.cpp:21:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
21 | ll mid=l+r>>1;
| ~^~
cake.cpp: In function 'll bs1(ll, ll, ll, ll, ll)':
cake.cpp:30:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | ll mid=l+r>>1;
| ~^~
cake.cpp: In function 'll bs2(ll, ll, ll, ll, ll)':
cake.cpp:39:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | ll mid=l+r>>1;
| ~^~
cake.cpp: In function 'll get(ll, ll, ll, ll, ll)':
cake.cpp:48:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | ll mid=l+r>>1;
| ~^~
cake.cpp: In function 'void solve()':
cake.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0;i<vec.size();i++) in[vec[i].se]=true;
| ~^~~~~~~~~~~
cake.cpp:113:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i=0;i<vec.size();i++) if(vec[i].se==id) vec[i].fi=newval;
| ~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
4 ms |
340 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1112 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
214 ms |
5284 KB |
Output is correct |
| 2 |
Correct |
161 ms |
5308 KB |
Output is correct |
| 3 |
Correct |
170 ms |
5320 KB |
Output is correct |
| 4 |
Correct |
146 ms |
5304 KB |
Output is correct |
| 5 |
Correct |
244 ms |
6176 KB |
Output is correct |
| 6 |
Correct |
183 ms |
6480 KB |
Output is correct |
| 7 |
Correct |
165 ms |
6312 KB |
Output is correct |
| 8 |
Correct |
149 ms |
6572 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
91 ms |
6812 KB |
Output is correct |
| 2 |
Correct |
78 ms |
6696 KB |
Output is correct |
| 3 |
Correct |
63 ms |
6716 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
153 ms |
13772 KB |
Output is correct |
| 6 |
Correct |
140 ms |
13704 KB |
Output is correct |
| 7 |
Correct |
109 ms |
13496 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
984 KB |
Output is correct |
| 2 |
Correct |
25 ms |
1228 KB |
Output is correct |
| 3 |
Correct |
54 ms |
3804 KB |
Output is correct |
| 4 |
Correct |
81 ms |
3788 KB |
Output is correct |
| 5 |
Correct |
87 ms |
1784 KB |
Output is correct |
| 6 |
Correct |
169 ms |
5164 KB |
Output is correct |
| 7 |
Correct |
86 ms |
2976 KB |
Output is correct |
| 8 |
Correct |
105 ms |
7388 KB |
Output is correct |
| 9 |
Correct |
512 ms |
18524 KB |
Output is correct |
| 10 |
Correct |
255 ms |
5180 KB |
Output is correct |
| 11 |
Correct |
321 ms |
7056 KB |
Output is correct |
| 12 |
Correct |
521 ms |
16976 KB |
Output is correct |
| 13 |
Correct |
393 ms |
18612 KB |
Output is correct |
