oj.uz

Submission #154121

# Submission time Handle Problem Language Result Execution time Memory
154121 2019-09-18T12:35:43 Z mhy908 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 13560 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=600;
    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 376 KB Output is correct
2 Correct 2 ms 376 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 376 KB Output is correct
2 Correct 2 ms 376 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 376 KB Output is correct
2 Correct 2 ms 376 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 3241 ms 1540 KB Output is correct
8 Correct 3302 ms 1764 KB Output is correct
9 Correct 3615 ms 3160 KB Output is correct
10 Correct 2301 ms 3164 KB Output is correct
11 Correct 1734 ms 3192 KB Output is correct
12 Correct 3947 ms 3928 KB Output is correct
13 Correct 2085 ms 4344 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 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 3241 ms 1540 KB Output is correct
8 Correct 3302 ms 1764 KB Output is correct
9 Correct 3615 ms 3160 KB Output is correct
10 Correct 2301 ms 3164 KB Output is correct
11 Correct 1734 ms 3192 KB Output is correct
12 Correct 3947 ms 3928 KB Output is correct
13 Correct 2085 ms 4344 KB Output is correct
14 Correct 3282 ms 3508 KB Output is correct
15 Correct 4722 ms 3644 KB Output is correct
16 Correct 5352 ms 5200 KB Output is correct
17 Correct 5963 ms 6400 KB Output is correct
18 Correct 5749 ms 6216 KB Output is correct
19 Correct 5594 ms 6416 KB Output is correct
20 Correct 5913 ms 6272 KB Output is correct
21 Correct 5933 ms 6252 KB Output is correct
22 Correct 4042 ms 5852 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 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 3241 ms 1540 KB Output is correct
8 Correct 3302 ms 1764 KB Output is correct
9 Correct 3615 ms 3160 KB Output is correct
10 Correct 2301 ms 3164 KB Output is correct
11 Correct 1734 ms 3192 KB Output is correct
12 Correct 3947 ms 3928 KB Output is correct
13 Correct 2085 ms 4344 KB Output is correct
14 Correct 3282 ms 3508 KB Output is correct
15 Correct 4722 ms 3644 KB Output is correct
16 Correct 5352 ms 5200 KB Output is correct
17 Correct 5963 ms 6400 KB Output is correct
18 Correct 5749 ms 6216 KB Output is correct
19 Correct 5594 ms 6416 KB Output is correct
20 Correct 5913 ms 6272 KB Output is correct
21 Correct 5933 ms 6252 KB Output is correct
22 Correct 4042 ms 5852 KB Output is correct
23 Execution timed out 9016 ms 13560 KB Time limit exceeded
24 Halted 0 ms 0 KB -