oj.uz

Submission #153245

# Submission time Handle Problem Language Result Execution time Memory
153245 2019-09-13T02:51:46 Z mhy908 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 4522 ms 8268 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();
}
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)return f(basketnum+1, pl);
    int p=bas[basketnum].find_pl(pl);
    //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++;
    //puts("");
    if(updatenum%sq){
        int wbas=find_basket(1, basnum, eleph[i]);
        int to=find_basket(1, basnum, 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 348 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 348 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 3 ms 376 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 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 3 ms 376 KB Output is correct
7 Correct 602 ms 3568 KB Output is correct
8 Correct 786 ms 3960 KB Output is correct
9 Correct 1545 ms 6680 KB Output is correct
10 Correct 1119 ms 6268 KB Output is correct
11 Correct 1036 ms 6264 KB Output is correct
12 Correct 2556 ms 6376 KB Output is correct
13 Correct 995 ms 6020 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 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 3 ms 376 KB Output is correct
7 Correct 602 ms 3568 KB Output is correct
8 Correct 786 ms 3960 KB Output is correct
9 Correct 1545 ms 6680 KB Output is correct
10 Correct 1119 ms 6268 KB Output is correct
11 Correct 1036 ms 6264 KB Output is correct
12 Correct 2556 ms 6376 KB Output is correct
13 Correct 995 ms 6020 KB Output is correct
14 Correct 942 ms 5140 KB Output is correct
15 Correct 1514 ms 5124 KB Output is correct
16 Correct 3606 ms 7060 KB Output is correct
17 Correct 4522 ms 8268 KB Output is correct
18 Correct 4463 ms 8184 KB Output is correct
19 Incorrect 45 ms 8184 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 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 3 ms 376 KB Output is correct
7 Correct 602 ms 3568 KB Output is correct
8 Correct 786 ms 3960 KB Output is correct
9 Correct 1545 ms 6680 KB Output is correct
10 Correct 1119 ms 6268 KB Output is correct
11 Correct 1036 ms 6264 KB Output is correct
12 Correct 2556 ms 6376 KB Output is correct
13 Correct 995 ms 6020 KB Output is correct
14 Correct 942 ms 5140 KB Output is correct
15 Correct 1514 ms 5124 KB Output is correct
16 Correct 3606 ms 7060 KB Output is correct
17 Correct 4522 ms 8268 KB Output is correct
18 Correct 4463 ms 8184 KB Output is correct
19 Incorrect 45 ms 8184 KB Output isn't correct
20 Halted 0 ms 0 KB -