| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 728767 |
2023-04-23T05:09:08 Z |
fdnfksd |
Cake (CEOI14_cake) |
C++14 |
|
358 ms |
12312 KB |
#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]);
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()>10)
{
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:102: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]
102 | for(int i=0;i<vec.size();i++) if(vec[i].se==id) vec[i].fi=newval;
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
130 ms |
980 KB |
Output isn't correct |
| 2 |
Incorrect |
124 ms |
984 KB |
Output isn't correct |
| 3 |
Incorrect |
130 ms |
984 KB |
Output isn't correct |
| 4 |
Incorrect |
134 ms |
984 KB |
Output isn't correct |
| 5 |
Incorrect |
147 ms |
1504 KB |
Output isn't correct |
| 6 |
Incorrect |
142 ms |
1496 KB |
Output isn't correct |
| 7 |
Incorrect |
160 ms |
1524 KB |
Output isn't correct |
| 8 |
Incorrect |
148 ms |
1612 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
5460 KB |
Output isn't correct |
| 2 |
Incorrect |
74 ms |
5312 KB |
Output isn't correct |
| 3 |
Incorrect |
62 ms |
5228 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 5 |
Incorrect |
126 ms |
11324 KB |
Output isn't correct |
| 6 |
Incorrect |
136 ms |
11308 KB |
Output isn't correct |
| 7 |
Incorrect |
104 ms |
10936 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
596 KB |
Output isn't correct |
| 2 |
Incorrect |
18 ms |
832 KB |
Output isn't correct |
| 3 |
Incorrect |
47 ms |
2884 KB |
Output isn't correct |
| 4 |
Incorrect |
49 ms |
2876 KB |
Output isn't correct |
| 5 |
Incorrect |
58 ms |
692 KB |
Output isn't correct |
| 6 |
Incorrect |
77 ms |
4048 KB |
Output isn't correct |
| 7 |
Incorrect |
70 ms |
1360 KB |
Output isn't correct |
| 8 |
Incorrect |
84 ms |
4972 KB |
Output isn't correct |
| 9 |
Incorrect |
302 ms |
12308 KB |
Output isn't correct |
| 10 |
Incorrect |
174 ms |
1444 KB |
Output isn't correct |
| 11 |
Incorrect |
202 ms |
2776 KB |
Output isn't correct |
| 12 |
Incorrect |
358 ms |
10956 KB |
Output isn't correct |
| 13 |
Incorrect |
272 ms |
12312 KB |
Output isn't correct |
