oj.uz

Submission #154125

# Submission time Handle Problem Language Result Execution time Memory
154125 2019-09-18T12:39:53 Z mhy908 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 15140 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=200;
    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 380 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 380 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 952 ms 2044 KB Output is correct
8 Correct 1063 ms 2468 KB Output is correct
9 Correct 1441 ms 5176 KB Output is correct
10 Correct 1580 ms 5240 KB Output is correct
11 Correct 1498 ms 5176 KB Output is correct
12 Correct 2530 ms 5316 KB Output is correct
13 Correct 1370 ms 5172 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 380 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 952 ms 2044 KB Output is correct
8 Correct 1063 ms 2468 KB Output is correct
9 Correct 1441 ms 5176 KB Output is correct
10 Correct 1580 ms 5240 KB Output is correct
11 Correct 1498 ms 5176 KB Output is correct
12 Correct 2530 ms 5316 KB Output is correct
13 Correct 1370 ms 5172 KB Output is correct
14 Correct 1079 ms 2952 KB Output is correct
15 Correct 1807 ms 3224 KB Output is correct
16 Correct 3689 ms 5496 KB Output is correct
17 Correct 4637 ms 7372 KB Output is correct
18 Correct 4591 ms 7228 KB Output is correct
19 Correct 3268 ms 8624 KB Output is correct
20 Correct 4684 ms 9004 KB Output is correct
21 Correct 4613 ms 8500 KB Output is correct
22 Correct 2564 ms 8236 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 380 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 952 ms 2044 KB Output is correct
8 Correct 1063 ms 2468 KB Output is correct
9 Correct 1441 ms 5176 KB Output is correct
10 Correct 1580 ms 5240 KB Output is correct
11 Correct 1498 ms 5176 KB Output is correct
12 Correct 2530 ms 5316 KB Output is correct
13 Correct 1370 ms 5172 KB Output is correct
14 Correct 1079 ms 2952 KB Output is correct
15 Correct 1807 ms 3224 KB Output is correct
16 Correct 3689 ms 5496 KB Output is correct
17 Correct 4637 ms 7372 KB Output is correct
18 Correct 4591 ms 7228 KB Output is correct
19 Correct 3268 ms 8624 KB Output is correct
20 Correct 4684 ms 9004 KB Output is correct
21 Correct 4613 ms 8500 KB Output is correct
22 Correct 2564 ms 8236 KB Output is correct
23 Execution timed out 9070 ms 15140 KB Time limit exceeded
24 Halted 0 ms 0 KB -