oj.uz

Submission #154122

# Submission time Handle Problem Language Result Execution time Memory
154122 2019-09-18T12:37:39 Z mhy908 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 9336 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=500;
    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 348 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 348 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 348 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 2725 ms 2492 KB Output is correct
8 Correct 2765 ms 2832 KB Output is correct
9 Correct 3177 ms 4780 KB Output is correct
10 Correct 3010 ms 4732 KB Output is correct
11 Correct 2548 ms 4644 KB Output is correct
12 Correct 3561 ms 4916 KB Output is correct
13 Correct 2804 ms 4144 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 348 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 2725 ms 2492 KB Output is correct
8 Correct 2765 ms 2832 KB Output is correct
9 Correct 3177 ms 4780 KB Output is correct
10 Correct 3010 ms 4732 KB Output is correct
11 Correct 2548 ms 4644 KB Output is correct
12 Correct 3561 ms 4916 KB Output is correct
13 Correct 2804 ms 4144 KB Output is correct
14 Correct 2836 ms 2964 KB Output is correct
15 Correct 4075 ms 3116 KB Output is correct
16 Correct 4756 ms 4460 KB Output is correct
17 Correct 5378 ms 5484 KB Output is correct
18 Correct 5280 ms 5472 KB Output is correct
19 Correct 4891 ms 5072 KB Output is correct
20 Correct 5490 ms 5120 KB Output is correct
21 Correct 5415 ms 5116 KB Output is correct
22 Correct 4161 ms 4688 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 348 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 2725 ms 2492 KB Output is correct
8 Correct 2765 ms 2832 KB Output is correct
9 Correct 3177 ms 4780 KB Output is correct
10 Correct 3010 ms 4732 KB Output is correct
11 Correct 2548 ms 4644 KB Output is correct
12 Correct 3561 ms 4916 KB Output is correct
13 Correct 2804 ms 4144 KB Output is correct
14 Correct 2836 ms 2964 KB Output is correct
15 Correct 4075 ms 3116 KB Output is correct
16 Correct 4756 ms 4460 KB Output is correct
17 Correct 5378 ms 5484 KB Output is correct
18 Correct 5280 ms 5472 KB Output is correct
19 Correct 4891 ms 5072 KB Output is correct
20 Correct 5490 ms 5120 KB Output is correct
21 Correct 5415 ms 5116 KB Output is correct
22 Correct 4161 ms 4688 KB Output is correct
23 Execution timed out 9087 ms 9336 KB Time limit exceeded
24 Halted 0 ms 0 KB -