oj.uz

Submission #153250

# Submission time Handle Problem Language Result Execution time Memory
153250 2019-09-13T03:39:21 Z mhy908 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 7584 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[800], siz;
    int next[800], cost[800];
    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[400];
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=(int)floor(sqrt(n));
    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 380 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 380 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 504 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 380 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 615 ms 2212 KB Output is correct
8 Correct 804 ms 2464 KB Output is correct
9 Correct 1546 ms 3740 KB Output is correct
10 Correct 1106 ms 3708 KB Output is correct
11 Correct 1014 ms 3744 KB Output is correct
12 Correct 2534 ms 3704 KB Output is correct
13 Correct 968 ms 3704 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 380 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 615 ms 2212 KB Output is correct
8 Correct 804 ms 2464 KB Output is correct
9 Correct 1546 ms 3740 KB Output is correct
10 Correct 1106 ms 3708 KB Output is correct
11 Correct 1014 ms 3744 KB Output is correct
12 Correct 2534 ms 3704 KB Output is correct
13 Correct 968 ms 3704 KB Output is correct
14 Correct 1008 ms 2696 KB Output is correct
15 Correct 1521 ms 2972 KB Output is correct
16 Correct 3578 ms 3960 KB Output is correct
17 Correct 4517 ms 4560 KB Output is correct
18 Correct 4428 ms 4556 KB Output is correct
19 Correct 3269 ms 4444 KB Output is correct
20 Correct 4522 ms 4564 KB Output is correct
21 Correct 4464 ms 4552 KB Output is correct
22 Correct 1752 ms 4600 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 380 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 615 ms 2212 KB Output is correct
8 Correct 804 ms 2464 KB Output is correct
9 Correct 1546 ms 3740 KB Output is correct
10 Correct 1106 ms 3708 KB Output is correct
11 Correct 1014 ms 3744 KB Output is correct
12 Correct 2534 ms 3704 KB Output is correct
13 Correct 968 ms 3704 KB Output is correct
14 Correct 1008 ms 2696 KB Output is correct
15 Correct 1521 ms 2972 KB Output is correct
16 Correct 3578 ms 3960 KB Output is correct
17 Correct 4517 ms 4560 KB Output is correct
18 Correct 4428 ms 4556 KB Output is correct
19 Correct 3269 ms 4444 KB Output is correct
20 Correct 4522 ms 4564 KB Output is correct
21 Correct 4464 ms 4552 KB Output is correct
22 Correct 1752 ms 4600 KB Output is correct
23 Execution timed out 9078 ms 7584 KB Time limit exceeded
24 Halted 0 ms 0 KB -