Submission #728774

#	Time	Username	Problem	Language	Result	Execution time	Memory
728774		fdnfksd	Cake (CEOI14_cake)	C++14	100 / 100	521 ms	18612 KiB

cake

#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 (stderr)

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;
      |                             ~^~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50