Submission #727806

#	Time	Username	Problem	Language	Result	Execution time	Memory
727806		onepunchac168	Dancing Elephants (IOI11_elephants)	C++17	0 / 100	2 ms	3924 KiB

elephants

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

//#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
//#pragma GCC target("sse4,avx2,fma")
#define task ""
#define ldb long double
#define pb push_back
#define fi first
#define se second
#define pc pop_back()
#define all(x) begin(x),end(x)
#define uniquev(v) v.resize(unique(all(v))-v.begin())
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define cntbit(v) __builtin_popcountll(v)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) ((1LL*a*b)/__gcd(a,b))
#define mask(x) (1LL<<(x))
#define readbit(x,i) ((x>>i)&1)
#define ins insert

typedef int ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;

ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};

const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const int maxn=1e6+5;
const int mod=1e9+7;
const char nl = '\n';
inline int ReadInt()
{
    char co;
    for (co = getchar(); co < '0' || co > '9'; co = getchar());
    int xo = co - '0';
    for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
        xo = xo * 10 + co - '0';
    return xo;
}

void WriteInt(int xo)
{
    if (xo > 9)
        WriteInt(xo / 10);
    putchar(xo % 10 + '0');
}
/* END OF TEMPLATE*/

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

int n,l;
const int BLOCK=501;
ll x[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--;
        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/BLOCK;i++)
    {
        for (int j=1;j<=b[i].sz;j++)
        {
            x[id]=b[i].a[j];
            id++;
        }
    }
    for (int i=0;i<=n;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];
    }
    for (int i=0;i<=n/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;
    for (int i=n/BLOCK;i>=0;i--)
    {
        if (b[i].sz>0)
        {
            if (b[i].a[1]<=x[aa])
            {
                bl1=i;
                break;
            }
        }
    }
    for (int i=n/BLOCK;i>=0;i--)
    {
        if (b[i].sz>0)
        {
            if (b[i].a[1]<=y)
            {
                bl2=i;
                break;
            }
        }
    }
    b[bl1].erase(x[aa]);
    b[bl2].insert(y);
    x[aa]=y;
    ll ok=l;
    ll gg;
    ll dd=0;
    for (int i=0;i<=n/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;
            }
        }
    }
    return res;
}

Compilation message (stderr)

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:130:25: warning: 'bl1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  130 |         for (int i=1;i<=sz;i++)
      |                         ^~
elephants.cpp:221:8: note: 'bl1' was declared here
  221 |     ll bl1;
      |        ^~~
elephants.cpp:279:36: warning: 'gg' may be used uninitialized in this function [-Wmaybe-uninitialized]
  279 |                     if (b[i].a[mid]-gg+ok<=l)
      |                         ~~~~~~~~~~~^~~
elephants.cpp:129:12: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
  129 |         ll id;
      |            ^~
elephants.cpp:109:14: warning: 'bl2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |         a[id]=val;
      |         ~~~~~^~~~
elephants.cpp:222:8: note: 'bl2' was declared here
  222 |     ll bl2;
      |        ^~~

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