oj.uz

Submission #153249

# Submission time Handle Problem Language Result Execution time Memory
153249 2019-09-13T03:33:58 Z mhy908 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 8536 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[1000], siz;
    int next[1000], cost[1000];
    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];
        }
        el[siz]=0;
        next[siz]=0;
        cost[siz]=0;
        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 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 504 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 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 599 ms 2460 KB Output is correct
8 Correct 771 ms 2808 KB Output is correct
9 Correct 1483 ms 4216 KB Output is correct
10 Correct 1101 ms 4216 KB Output is correct
11 Correct 999 ms 4216 KB Output is correct
12 Correct 2503 ms 4216 KB Output is correct
13 Correct 976 ms 4216 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 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 599 ms 2460 KB Output is correct
8 Correct 771 ms 2808 KB Output is correct
9 Correct 1483 ms 4216 KB Output is correct
10 Correct 1101 ms 4216 KB Output is correct
11 Correct 999 ms 4216 KB Output is correct
12 Correct 2503 ms 4216 KB Output is correct
13 Correct 976 ms 4216 KB Output is correct
14 Correct 992 ms 2908 KB Output is correct
15 Correct 1488 ms 3320 KB Output is correct
16 Correct 3559 ms 4452 KB Output is correct
17 Correct 4499 ms 5116 KB Output is correct
18 Correct 4381 ms 5176 KB Output is correct
19 Correct 3245 ms 5296 KB Output is correct
20 Correct 4499 ms 5368 KB Output is correct
21 Correct 4391 ms 5368 KB Output is correct
22 Correct 1717 ms 5288 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 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 599 ms 2460 KB Output is correct
8 Correct 771 ms 2808 KB Output is correct
9 Correct 1483 ms 4216 KB Output is correct
10 Correct 1101 ms 4216 KB Output is correct
11 Correct 999 ms 4216 KB Output is correct
12 Correct 2503 ms 4216 KB Output is correct
13 Correct 976 ms 4216 KB Output is correct
14 Correct 992 ms 2908 KB Output is correct
15 Correct 1488 ms 3320 KB Output is correct
16 Correct 3559 ms 4452 KB Output is correct
17 Correct 4499 ms 5116 KB Output is correct
18 Correct 4381 ms 5176 KB Output is correct
19 Correct 3245 ms 5296 KB Output is correct
20 Correct 4499 ms 5368 KB Output is correct
21 Correct 4391 ms 5368 KB Output is correct
22 Correct 1717 ms 5288 KB Output is correct
23 Execution timed out 9063 ms 8536 KB Time limit exceeded
24 Halted 0 ms 0 KB -