oj.uz

Submission #153247

# Submission time Handle Problem Language Result Execution time Memory
153247 2019-09-13T03:24:18 Z mhy908 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 15408 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
int n, sq, l, rea[150010], eleph[150010], bnum[150010], basnum, updatenum;
struct data
{
    int el[5000], siz;
    int next[5000], cost[5000];
    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[5000];
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 2 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 2 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 598 ms 2668 KB Output is correct
8 Correct 772 ms 3028 KB Output is correct
9 Correct 1500 ms 4984 KB Output is correct
10 Correct 1108 ms 4896 KB Output is correct
11 Correct 1004 ms 4896 KB Output is correct
12 Correct 2546 ms 5044 KB Output is correct
13 Correct 974 ms 4984 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 2 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 598 ms 2668 KB Output is correct
8 Correct 772 ms 3028 KB Output is correct
9 Correct 1500 ms 4984 KB Output is correct
10 Correct 1108 ms 4896 KB Output is correct
11 Correct 1004 ms 4896 KB Output is correct
12 Correct 2546 ms 5044 KB Output is correct
13 Correct 974 ms 4984 KB Output is correct
14 Correct 1000 ms 3384 KB Output is correct
15 Correct 1497 ms 3908 KB Output is correct
16 Correct 3583 ms 5128 KB Output is correct
17 Correct 4495 ms 6312 KB Output is correct
18 Correct 4390 ms 6240 KB Output is correct
19 Correct 3264 ms 6084 KB Output is correct
20 Correct 4533 ms 8276 KB Output is correct
21 Correct 4393 ms 8344 KB Output is correct
22 Correct 1705 ms 7772 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 2 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 598 ms 2668 KB Output is correct
8 Correct 772 ms 3028 KB Output is correct
9 Correct 1500 ms 4984 KB Output is correct
10 Correct 1108 ms 4896 KB Output is correct
11 Correct 1004 ms 4896 KB Output is correct
12 Correct 2546 ms 5044 KB Output is correct
13 Correct 974 ms 4984 KB Output is correct
14 Correct 1000 ms 3384 KB Output is correct
15 Correct 1497 ms 3908 KB Output is correct
16 Correct 3583 ms 5128 KB Output is correct
17 Correct 4495 ms 6312 KB Output is correct
18 Correct 4390 ms 6240 KB Output is correct
19 Correct 3264 ms 6084 KB Output is correct
20 Correct 4533 ms 8276 KB Output is correct
21 Correct 4393 ms 8344 KB Output is correct
22 Correct 1705 ms 7772 KB Output is correct
23 Execution timed out 9008 ms 15408 KB Time limit exceeded
24 Halted 0 ms 0 KB -