Submission #153175

#	Time	Username	Problem	Language	Result	Execution time	Memory
153175		mhy908	Dancing Elephants (IOI11_elephants)	C++14	10 / 100	2 ms	376 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 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--;
    }
    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]);
}

/*
20 30 80
36
64
99
125
150
183
211
239
265
291
319
346
373
407
432
463
488
523
551
583
19 683 11
18 651 12
17 623 11
16 588 12
15 563 11
14 532 12
13 507 11
12 473 12
11 446 11
10 419 12
9 391 11
8 365 12
7 339 11
6 311 12
5 283 11
4 250 11
3 225 11
2 199 11
1 164 12
0 136 11
19 783 11
18 751 12
17 723 11
16 688 12
15 663 11
14 632 12
13 607 11
12 573 12
11 546 11
10 519 12
9 491 11
8 465 12
7 439 11
6 411 12
5 383 11
4 350 11
3 325 11
2 299 11
1 264 12
0 236 11
19 883 11
18 851 12
17 823 11
16 788 12
15 763 11
14 732 12
13 707 11
12 673 12
11 646 11
10 619 12
9 591 11
8 565 12
7 539 11
6 511 12
5 483 11
4 450 11
3 425 11
2 399 11
1 364 12
0 336 11
19 983 11
18 951 12
17 923 11
16 888 12
15 863 11
14 832 12
13 807 11
12 773 12
11 746 11
10 719 12
9 691 11
8 665 12
7 639 11
6 611 12
5 583 11
4 550 11
3 525 11
2 499 11
1 464 12
0 436 11

*/

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