#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 <<
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]);
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());
while(vec.size()>0)
{
in[vec.back().se]=false;
vec.pop_back();
}
}
}
}
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:103: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]
103 | for(int i=0;i<vec.size();i++) if(vec[i].se==id) vec[i].fi=newval;
| ~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
115 ms |
5304 KB |
Output isn't correct |
| 2 |
Incorrect |
107 ms |
5324 KB |
Output isn't correct |
| 3 |
Incorrect |
112 ms |
5316 KB |
Output isn't correct |
| 4 |
Incorrect |
108 ms |
5436 KB |
Output isn't correct |
| 5 |
Incorrect |
123 ms |
6188 KB |
Output isn't correct |
| 6 |
Incorrect |
123 ms |
6580 KB |
Output isn't correct |
| 7 |
Incorrect |
125 ms |
6456 KB |
Output isn't correct |
| 8 |
Incorrect |
116 ms |
6580 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
77 ms |
6800 KB |
Output isn't correct |
| 2 |
Incorrect |
69 ms |
6748 KB |
Output isn't correct |
| 3 |
Incorrect |
61 ms |
6504 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 5 |
Incorrect |
121 ms |
13812 KB |
Output isn't correct |
| 6 |
Incorrect |
135 ms |
13652 KB |
Output isn't correct |
| 7 |
Incorrect |
99 ms |
13480 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
18 ms |
984 KB |
Output isn't correct |
| 2 |
Incorrect |
19 ms |
1144 KB |
Output isn't correct |
| 3 |
Incorrect |
45 ms |
3776 KB |
Output isn't correct |
| 4 |
Incorrect |
43 ms |
3912 KB |
Output isn't correct |
| 5 |
Incorrect |
47 ms |
1768 KB |
Output isn't correct |
| 6 |
Incorrect |
77 ms |
5168 KB |
Output isn't correct |
| 7 |
Incorrect |
66 ms |
2964 KB |
Output isn't correct |
| 8 |
Incorrect |
82 ms |
7384 KB |
Output isn't correct |
| 9 |
Incorrect |
305 ms |
18704 KB |
Output isn't correct |
| 10 |
Incorrect |
151 ms |
5188 KB |
Output isn't correct |
| 11 |
Incorrect |
175 ms |
6996 KB |
Output isn't correct |
| 12 |
Incorrect |
287 ms |
17032 KB |
Output isn't correct |
| 13 |
Incorrect |
270 ms |
18624 KB |
Output isn't correct |
