oj.uz

Submission #154123

# Submission time Handle Problem Language Result Execution time Memory
154123 2019-09-18T12:38:42 Z mhy908 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 11580 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, sq, l, rea[150010], eleph[150010], basnum, updatenum;
struct data
{
    int el[1600], siz;
    int next[1600], cost[1600];
    void in_init(int p)
    {
        el[++siz]=p;
    }
    void get_arr()
    {
        for(int here=siz; here>=1; here--){
            int ne=el[here]+l+1;
            if(ne>el[siz]){
                cost[here]=1;
                next[here]=ne;
            }
            else{
                int dow=lower_bound(el, el+siz+1, ne)-el;
                cost[here]=cost[dow]+1;
                next[here]=next[dow];
            }
        }
    }
    void in(int p)
    {
        int here;
        if(!siz)here=1;
        else here=lower_bound(el, el+siz+1, p)-el;
        here=max(here, 1);
        for(int i=siz; i>=here; i--)el[i+1]=el[i], next[i+1]=next[i], cost[i+1]=cost[i];
        el[here]=p;
        siz++;
        get_arr();
    }
    void out(int p)
    {
        int here=lower_bound(el, el+siz+1, p)-el;
        for(int i=here+1; i<=siz; i++){
            el[i-1]=el[i];
            next[i-1]=next[i];
            cost[i-1]=cost[i];
        }
        siz--;
        get_arr();
    }
    int find_pl(int p){
        return lower_bound(el+1, el+siz+1, p)-el;
    }
}bas[1000];
void in_basket()
{
    basnum=1;
    for(int i=1; i<=n; i++){
        bas[basnum].in_init(rea[i]);
        if(i%sq==0&&i!=n)basnum++;
    }
    for(int i=1; i<=basnum; i++)
        bas[i].get_arr();
}
void init(int N, int L, int X[])
{
    n=N;
    l=L;
    sq=300;
    for(int i=0; i<n; i++)rea[i+1]=eleph[i]=X[i];
    sort(rea+1, rea+n+1);
    in_basket();
    //puts("");
}
int find_basket(int st, int fin, int num)
{
    if(st==fin)return st;
    int mid=(st+fin)/2+1;
    if(bas[mid].el[1]>num)return find_basket(st, mid-1, num);
    return find_basket(mid, fin, num);
}
int f(int basketnum, int pl)
{
    if(basketnum>basnum)return 0;
    if(bas[basketnum].el[bas[basketnum].siz]<pl||bas[basketnum].siz==0)return f(basketnum+1, pl);
    int p=bas[basketnum].find_pl(pl);
    //if(updatenum==41)printf("%d, %d\n", bas[basketnum].el[p], bas[basketnum].cost[p]);
    return bas[basketnum].cost[p]+f(basketnum+1, bas[basketnum].next[p]);
}
int update(int i, int y)
{
    updatenum++;
    if(updatenum%sq){
        int wbas, to;
        if(bas[basnum].siz){
            wbas=find_basket(1, basnum, eleph[i]);
            to=find_basket(1, basnum, y);
        }
        else{
            wbas=find_basket(1, basnum-1, eleph[i]);
            to=find_basket(1, basnum-1, y);
        }
        bas[wbas].out(eleph[i]);
        bas[to].in(y);
        eleph[i]=y;
    }
    else{
        eleph[i]=y;
        for(int i=0; i<n; i++)rea[i+1]=eleph[i];
        sort(rea+1, rea+n+1);
        for(int i=1; i<=basnum; i++)bas[i].siz=0;
        in_basket();
    }
    return f(1, bas[1].el[1]);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 420 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1517 ms 1796 KB Output is correct
8 Correct 1602 ms 2116 KB Output is correct
9 Correct 1999 ms 4172 KB Output is correct
10 Correct 1622 ms 4088 KB Output is correct
11 Correct 1458 ms 4180 KB Output is correct
12 Correct 2668 ms 4320 KB Output is correct
13 Correct 1391 ms 4184 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 420 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1517 ms 1796 KB Output is correct
8 Correct 1602 ms 2116 KB Output is correct
9 Correct 1999 ms 4172 KB Output is correct
10 Correct 1622 ms 4088 KB Output is correct
11 Correct 1458 ms 4180 KB Output is correct
12 Correct 2668 ms 4320 KB Output is correct
13 Correct 1391 ms 4184 KB Output is correct
14 Correct 1615 ms 2760 KB Output is correct
15 Correct 2516 ms 2844 KB Output is correct
16 Correct 3734 ms 4468 KB Output is correct
17 Correct 4488 ms 5892 KB Output is correct
18 Correct 4383 ms 5884 KB Output is correct
19 Correct 3496 ms 5696 KB Output is correct
20 Correct 4501 ms 5752 KB Output is correct
21 Correct 4387 ms 5952 KB Output is correct
22 Correct 1868 ms 5628 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 420 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1517 ms 1796 KB Output is correct
8 Correct 1602 ms 2116 KB Output is correct
9 Correct 1999 ms 4172 KB Output is correct
10 Correct 1622 ms 4088 KB Output is correct
11 Correct 1458 ms 4180 KB Output is correct
12 Correct 2668 ms 4320 KB Output is correct
13 Correct 1391 ms 4184 KB Output is correct
14 Correct 1615 ms 2760 KB Output is correct
15 Correct 2516 ms 2844 KB Output is correct
16 Correct 3734 ms 4468 KB Output is correct
17 Correct 4488 ms 5892 KB Output is correct
18 Correct 4383 ms 5884 KB Output is correct
19 Correct 3496 ms 5696 KB Output is correct
20 Correct 4501 ms 5752 KB Output is correct
21 Correct 4387 ms 5952 KB Output is correct
22 Correct 1868 ms 5628 KB Output is correct
23 Execution timed out 9017 ms 11580 KB Time limit exceeded
24 Halted 0 ms 0 KB -