Submission #727848

#	Time	Username	Problem	Language	Result	Execution time	Memory
727848		onepunchac168	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	2855 ms	12484 KiB

elephants

// created by Dinh Manh Hung
// onepunchac168
// THPT CHUYEN HA TINH
// HA TINH, VIET NAM
#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;

#define fi first
#define se second
#define pb push_back
typedef int ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;
const char nl = '\n';
/* END OF TEMPLATE*/

// ================= Solution =================//

int n,l;
const int BLOCK=501;
ll x[150005];
ll yx[150005];
struct Siuuu{
    ii dp[505*2];
    ll a[505*2];
    ll sz;
    void build(vector <ll> opt)
    {
        sz=opt.size();
        ll id=sz;
        for (int i=sz;i>=1;i--)
        {
            a[i]=opt[i-1];
            while (a[id]-a[i]>l)
            {
                id--;
            }
            if (id==sz)
            {
                dp[i]={1,a[id]-a[i]};
            }
            else
            {
                dp[i]={dp[id+1].fi+1,dp[id+1].se};
            }
        }
    }
    void insert(ll val)
    {
        ll id=sz+1;
        for (int i=1;i<=sz;i++)
        {
            if (a[i]<=val)
            {

            }
            else
            {
                id=i;
                break;
            }
        }
        sz++;
        for (int i=sz;i>id;i--)
        {
            a[i]=a[i-1];
        }
        a[id]=val;
        id=sz;
        for (int i=sz;i>=1;i--)
        {
            while (a[id]-a[i]>l)
            {
                id--;
            }
            if (id==sz)
            {
                dp[i]={1,a[id]-a[i]};
            }
            else
            {
                dp[i]={dp[id+1].fi+1,dp[id+1].se};
            }
        }
    }
    void erase(ll val)
    {
        ll id;
        for (int i=1;i<=sz;i++)
        {
            if (a[i]<val)
            {

            }
            else
            {
                id=i;
                break;
            }
        }
        sz--;
        if (sz==0)
        {
            return;
        }
        for (int i=id;i<=sz;i++)
        {
            a[i]=a[i+1];
        }
        id=sz;
        for (int i=sz;i>=1;i--)
        {
            while (a[id]-a[i]>l)
            {
                id--;
            }
            if (id==sz)
            {
                dp[i]={1,a[id]-a[i]};
            }
            else
            {
                dp[i]={dp[id+1].fi+1,dp[id+1].se};
            }
        }
    }

} b[305];
void optmushnpr()
{
    ll id=0;
    for (int i=0;i<=(n-1)/BLOCK;i++)
    {
        for (int j=1;j<=b[i].sz;j++)
        {
            x[id]=b[i].a[j];
            id++;
        }
    }
    for (int i=0;i<=(n-1)/BLOCK;i++)
    {
        ll a1=BLOCK*i;
        ll a2=BLOCK*(i+1)-1;
        a2=min(a2,n-1);
        vector <ll> vt;
        for (int j=a1;j<=a2;j++)
        {
            vt.pb(x[j]);
        }
        b[i].build(vt);
    }
}
void init(int N, int L, int X[])
{
    n=N;
    l=L;
    for (int i=0;i<n;i++)
    {
        x[i]=X[i];
        yx[i]=X[i];
    }
    for (int i=0;i<=(n-1)/BLOCK;i++)
    {
        ll a1=BLOCK*i;
        ll a2=BLOCK*(i+1)-1;
        a2=min(a2,n-1);
        vector <ll> vt;
        for (int j=a1;j<=a2;j++)
        {
            vt.pb(x[j]);
        }
        b[i].build(vt);
    }
}
ll dem=0;
int update(int aa, int y)
{
    if (dem==400)
    {
        optmushnpr();
        dem=0;
    }
    dem++;
    ll res=0;
    ll bl1;
    ll bl2=0;
    for (int i=(n-1)/BLOCK;i>=0;i--)
    {
        if (b[i].sz>0)
        {
            if (b[i].a[1]<=yx[aa])
            {
                bl1=i;
                break;
            }
        }
    }
    for (int i=(n-1)/BLOCK;i>=0;i--)
    {
        if (b[i].sz>0)
        {
            if (b[i].a[1]<=y)
            {
                bl2=i;
                break;
            }
        }
    }
    b[bl1].erase(yx[aa]);
    b[bl2].insert(y);
    yx[aa]=y;
    ll ok=l;
    ll gg;
    ll dd=0;
    for (int i=0;i<=(n-1)/BLOCK;i++)
    {
        if (b[i].sz==0)
        {
            continue;
        }
        dd++;
        if (dd==1)
        {
            res=b[i].dp[1].fi;
            ok=b[i].dp[1].se;
            gg=b[i].a[b[i].sz];
        }
        else
        {
            if (b[i].a[b[i].sz]-gg+ok<=l)
            {
                ok+=b[i].a[b[i].sz]-gg;
                gg=b[i].a[b[i].sz];
            }
            else
            {
                int left=1;
                int right=b[i].sz;
                ll ans=0;
                while (left<=right)
                {
                    int mid=(left+right)/2;
                    if (b[i].a[mid]-gg+ok<=l)
                    {
                        ans=mid;
                        left=mid+1;
                    }
                    else right=mid-1;
                }
                res+=b[i].dp[ans+1].fi;
                ok=b[i].dp[ans+1].se;
                gg=b[i].a[b[i].sz];
            }
        }
    }
    return res;
}

Compilation message (stderr)

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:92:25: warning: 'bl1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |         for (int i=1;i<=sz;i++)
      |                         ^~
elephants.cpp:188:8: note: 'bl1' was declared here
  188 |     ll bl1;
      |        ^~~
elephants.cpp:246:36: warning: 'gg' may be used uninitialized in this function [-Wmaybe-uninitialized]
  246 |                     if (b[i].a[mid]-gg+ok<=l)
      |                         ~~~~~~~~~~~^~~
elephants.cpp:111:17: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |             a[i]=a[i+1];
      |             ~~~~^~~~~~~
elephants.cpp:91:12: note: 'id' was declared here
   91 |         ll id;
      |            ^~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3