Submission #443737

#	Time	Username	Problem	Language	Result	Execution time	Memory
443737		RGBB	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	3556 ms	12388 KiB

elephants

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//constants
const int MAXN=150000;
const int blk=400;
//important stuffs
int n,nb,l,cnt,arr[MAXN];
//elephant indices
int ind[MAXN];
//decomposition blocks
int pos[375][2*blk];
int val[375][2*blk];
int dis[375][2*blk];
//block sizes
int si[375];
//actual code
void recalc(int p){
    if(si[p]==0)return;
    int pnt=si[p];
    for(int i=si[p]-1;i>=0;i--){
        while(pos[p][pnt-1]-l>pos[p][i])pnt--;
        if(pnt==si[p]){
            val[p][i]=1;
            dis[p][i]=pos[p][i]+l;
        }
        else{
            val[p][i]=val[p][pnt]+1;
            dis[p][i]=dis[p][pnt];
        }
    }
}
void reconstruct(){
    int tc=0;
    for(int i=0;i<nb;i++){
        for(int j=0;j<si[i];j++)arr[tc++]=pos[i][j];
    }
    for(int i=0;i<nb;i++){
        for(int j=0;j<blk&&i*blk+j<n;j++){
            pos[i][j]=arr[i*blk+j];
            si[i]=j+1;
        }
        recalc(i);
    }
}
void sub(int p,int v){
    int tc=0;
    while(pos[p][tc]!=v)tc++;
    for(int i=tc+1;i<si[p];i++)pos[p][i-1]=pos[p][i];
    si[p]--;
}
void add(int p,int v){
    int tc=si[p];
    while(tc>0&&pos[p][tc-1]>v){
        pos[p][tc]=pos[p][tc-1];
        tc--;
    }
    pos[p][tc]=v;
    si[p]++;
}
int query(){
    int ret=0;
    int cp=-1;
    for(int i=0;i<nb;i++){
        if(si[i]==0||pos[i][si[i]-1]<=cp)continue;
        int bp=(int*)lower_bound(pos[i],pos[i]+si[i],cp+1)-pos[i];
        ret+=val[i][bp];
        cp=dis[i][bp];
    }
    return ret;
}
void init(int N,int L,int X[]){
    n=N;
    l=L;
    nb=ceil((double)n/blk);
    cnt=0;
    for(int i=0;i<n;i++)ind[i]=X[i];
    for(int i=0;i<nb;i++){
        for(int j=0;j<blk&&i*blk+j<n;j++){
            pos[i][j]=X[i*blk+j];
            si[i]=j+1;
        }
        recalc(i);
    }
}
int update(int i,int y){
    cnt++;
    if(cnt%blk==0)reconstruct();
    int tc=0;
    while(si[tc]==0||pos[tc][0]>ind[i]||pos[tc][si[tc]-1]<ind[i])tc++;
    sub(tc,ind[i]);
    recalc(tc);
    tc=0;
    int prev=INT_MIN;
    while(tc<nb-1&&(si[tc]==0||prev>y||pos[tc][si[tc]-1]<y)){
        if(si[tc]!=0)prev=pos[tc][si[tc]-1];
        tc++;
    }
    add(tc,y);
    recalc(tc);
    ind[i]=y;
    return query();
}
void output(){
    for(int i=0;i<nb;i++){
        for(int y=0;y<si[i];y++)cout<<pos[i][y]<<" ";
        cout<<"\n";
    }
    for(int i=0;i<nb;i++){
        for(int y=0;y<si[i];y++)cout<<val[i][y]<<" ";
        cout<<"\n";
    }
    for(int i=0;i<nb;i++){
        for(int y=0;y<si[i];y++)cout<<dis[i][y]<<" ";
        cout<<"\n";
    }
}

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