oj.uz

Submission #727837

# Submission time Handle Problem Language Result Execution time Memory
727837 2023-04-21T12:01:31 Z onepunchac168 Dancing Elephants (IOI11_elephants) C++14
26 / 100
 265 ms 6476 KB 
// 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];
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];
    }
    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]<=x[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(x[aa]);
    b[bl2].insert(y);
    x[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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct
3 Correct 2 ms 3924 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct
3 Correct 2 ms 3924 KB Output is correct
4 Correct 2 ms 3924 KB Output is correct
5 Correct 2 ms 3924 KB Output is correct
6 Correct 2 ms 3924 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct
3 Correct 2 ms 3924 KB Output is correct
4 Correct 2 ms 3924 KB Output is correct
5 Correct 2 ms 3924 KB Output is correct
6 Correct 2 ms 3924 KB Output is correct
7 Correct 196 ms 5528 KB Output is correct
8 Correct 200 ms 5684 KB Output is correct
9 Correct 265 ms 6476 KB Output is correct
10 Incorrect 146 ms 6320 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct
3 Correct 2 ms 3924 KB Output is correct
4 Correct 2 ms 3924 KB Output is correct
5 Correct 2 ms 3924 KB Output is correct
6 Correct 2 ms 3924 KB Output is correct
7 Correct 196 ms 5528 KB Output is correct
8 Correct 200 ms 5684 KB Output is correct
9 Correct 265 ms 6476 KB Output is correct
10 Incorrect 146 ms 6320 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct
3 Correct 2 ms 3924 KB Output is correct
4 Correct 2 ms 3924 KB Output is correct
5 Correct 2 ms 3924 KB Output is correct
6 Correct 2 ms 3924 KB Output is correct
7 Correct 196 ms 5528 KB Output is correct
8 Correct 200 ms 5684 KB Output is correct
9 Correct 265 ms 6476 KB Output is correct
10 Incorrect 146 ms 6320 KB Output isn't correct
11 Halted 0 ms 0 KB -