oj.uz

Submission #727848

# Submission time Handle Problem Language Result Execution time Memory
727848 2023-04-21T12:58:18 Z onepunchac168 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 2855 ms 12484 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];
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

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.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 3 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
24.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 3 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 200 ms 4804 KB Output is correct
8 Correct 202 ms 4832 KB Output is correct
9 Correct 269 ms 5340 KB Output is correct
10 Correct 267 ms 5248 KB Output is correct
11 Correct 239 ms 6392 KB Output is correct
12 Correct 498 ms 6532 KB Output is correct
13 Correct 264 ms 6236 KB Output is correct

Subtask #4
47.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 3 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 200 ms 4804 KB Output is correct
8 Correct 202 ms 4832 KB Output is correct
9 Correct 269 ms 5340 KB Output is correct
10 Correct 267 ms 5248 KB Output is correct
11 Correct 239 ms 6392 KB Output is correct
12 Correct 498 ms 6532 KB Output is correct
13 Correct 264 ms 6236 KB Output is correct
14 Correct 244 ms 6476 KB Output is correct
15 Correct 341 ms 6456 KB Output is correct
16 Correct 942 ms 7164 KB Output is correct
17 Correct 920 ms 7620 KB Output is correct
18 Correct 1004 ms 7552 KB Output is correct
19 Correct 456 ms 7756 KB Output is correct
20 Correct 953 ms 7620 KB Output is correct
21 Correct 877 ms 7608 KB Output is correct
22 Correct 447 ms 7188 KB Output is correct

Subtask #5
3.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 3 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 200 ms 4804 KB Output is correct
8 Correct 202 ms 4832 KB Output is correct
9 Correct 269 ms 5340 KB Output is correct
10 Correct 267 ms 5248 KB Output is correct
11 Correct 239 ms 6392 KB Output is correct
12 Correct 498 ms 6532 KB Output is correct
13 Correct 264 ms 6236 KB Output is correct
14 Correct 244 ms 6476 KB Output is correct
15 Correct 341 ms 6456 KB Output is correct
16 Correct 942 ms 7164 KB Output is correct
17 Correct 920 ms 7620 KB Output is correct
18 Correct 1004 ms 7552 KB Output is correct
19 Correct 456 ms 7756 KB Output is correct
20 Correct 953 ms 7620 KB Output is correct
21 Correct 877 ms 7608 KB Output is correct
22 Correct 447 ms 7188 KB Output is correct
23 Correct 2125 ms 12480 KB Output is correct
24 Correct 2413 ms 12484 KB Output is correct
25 Correct 1534 ms 12476 KB Output is correct
26 Correct 1850 ms 12480 KB Output is correct
27 Correct 1933 ms 12328 KB Output is correct
28 Correct 1151 ms 8756 KB Output is correct
29 Correct 1101 ms 8780 KB Output is correct
30 Correct 1245 ms 8684 KB Output is correct
31 Correct 1106 ms 8684 KB Output is correct
32 Correct 1280 ms 11908 KB Output is correct
33 Correct 1059 ms 11240 KB Output is correct
34 Correct 1475 ms 12216 KB Output is correct
35 Correct 1050 ms 12408 KB Output is correct
36 Correct 494 ms 11896 KB Output is correct
37 Correct 2080 ms 12308 KB Output is correct
38 Correct 1550 ms 11124 KB Output is correct
39 Correct 1531 ms 12152 KB Output is correct
40 Correct 1523 ms 11148 KB Output is correct
41 Correct 2855 ms 11904 KB Output is correct
42 Correct 2841 ms 12132 KB Output is correct