Submission #18016

#	Time	Username	Problem	Language	Result	Execution time	Memory
18016		comet	Dancing Elephants (IOI11_elephants)	C++98	100 / 100	8537 ms	22608 KiB

elephants

#include <cstdio>
#include <algorithm>
using namespace std;
 
int N,M,L;
int B=500;
 
struct group{
    int sz,p[1010],cnt[1010],nxt[1010];
    void init(){
        int id=sz-1;
        for(int i=sz-1;i>=0;i--){
            if(p[sz-1]-p[i]<=L)cnt[i]=1,nxt[i]=p[i]+L+1;
            else{
                while(p[id]-p[i]>L)id--;
                cnt[i]=cnt[id+1]+1;
                nxt[i]=nxt[id+1];
            }
        }
    }
    void push(int x){
        int id=0;
        while(id<sz&&p[id]<=x)id++;
        sz++;
        for(int i=sz-1;i>id;i--)p[i]=p[i-1];
        p[id]=x;
        init();
    }
    void pop(int x){
        int id=0;
        while(p[id]<=x)id++;
        for(int i=id;i<sz;i++)p[i-1]=p[i];
        sz--;
        init();
    }
}a[300];
 
struct elephant{
    int p,group_id,id;
    bool operator<(const elephant& r)const{
        return p<r.p;
    }
}b[150010];
 
int ID[150010];
 
void renewal(){
    sort(b,b+N);
    for(int i=0;i<M;i++)a[i].sz=0;
    for(int i=0;i<N;i++){
        ID[b[i].id]=i;
        b[i].group_id=i/B;
        a[i/B].p[a[i/B].sz++]=b[i].p;
        M=max(M,i/B+1);
    }
    for(int i=0;i<M;i++){
        a[i].init();
    }
}
 
void init(int N_, int L_, int X[]){
    N=N_;
    L=L_;
    for(int i=0;i<N;i++)b[i]=elephant{X[i],i/B,i};
    renewal();
}
 
int findGroup(int x){
    if(a[0].p[0]>x)return 0;
    for(int i=0;i<M-1;i++){
        if(a[i].p[0]<=x&&x<a[i+1].p[0])return i;
    }
    return M-1;
}
 
int calc(){
    int x=0,ret=0;
    for(int i=0;i<M;i++){
        int id=lower_bound(a[i].p,a[i].p+a[i].sz,x)-a[i].p;
        if(id==a[i].sz)continue;
        ret+=a[i].cnt[id];
        x=a[i].nxt[id];
    }
    return ret;
}
 
int update(int i, int y){
    int id=b[ID[i]].group_id;
    a[id].pop(b[ID[i]].p);
    b[ID[i]].p=y;
 	if(a[id].sz==0){
 		renewal();
 		return calc();
 	}
    id=b[ID[i]].group_id=findGroup(y);
    a[id].push(y);
    if(a[id].sz>1000)renewal();
    return calc();
}

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