Submission #153165

#	Time	Username	Problem	Language	Result	Execution time	Memory
153165		mhy908	Dancing Elephants (IOI11_elephants)	C++14	10 / 100	2 ms	504 KiB

elephants

#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[500], siz;
    int next[500], cost[500];
    void in_init(int p)
    {
        el[++siz]=p;
    }
    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=here; i<=siz; i++)el[i+1]=el[i], next[i+1]=next[i], cost[i+1]=cost[i];
        el[here]=p;
        siz++;
        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 out(int p)
    {
        int here=upper_bound(el, el+siz+1, eleph[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--;
    }
    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];
            }
        }
    }
    int find_pl(int p)
    {
        return lower_bound(el+1, el+siz+1, p)-el;
    }
}bas[500];
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);
    return bas[basketnum].cost[p]+f(basketnum+1, bas[basketnum].next[p]);
}
int update(int i, int y)
{
    updatenum++;
    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{
        updatenum=0;
        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]);
}

/*
4 10 5
10 15 17 20
2 16 1
1 25 2
3 35 2
0 38 2
2 0 3
*/

/*
10 15 17 20
10 15 16 20
10 25 16 20
10 25 16 35
38 25 16 35
38 25 0 35
*/

• Subtask 1: 10 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3