Submission #269748

#	Time	Username	Problem	Language	Result	Execution time	Memory
269748		teee	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	20 ms	2176 KiB

elephants

#include <iostream>
#include <algorithm>
#include "elephants.h"
using namespace std;
const int sz=388;
int l,mg,upcnt;
struct bucket{
    int val[sz<<1],cnt[sz<<1],last[sz<<1],size;
    void upd(){
        int t=size-1;
        for(int i=size-1;i>=0;i--){
            while(t!=i&&val[t-1]-val[i]>l)t--;
            if(val[size-1]-val[i]<=l) cnt[i]=1,last[i]=val[i]+l;
            else cnt[i]=cnt[t]+1,last[i]=last[t];
        }
    }
} buck[sz];
int arr[150'010], temp[150'010];
void refresh(){
    int cnt=0;
    for(int i=0;i<=mg;i++){
        for(int j=0;j<buck[i].size;j++){
            temp[cnt++]=buck[i].val[j];
        }buck[i].size=0;
    }
    int t=sz,tg=0;
    for(int i=0;i<cnt;i++){
        if(i==t) t+=sz,tg++;
        buck[tg].val[i-t+sz]=temp[i];
        buck[tg].size++;
    }
    for(int i=0;i<=mg;i++){
        buck[i].upd();
    }
    upcnt=0;
}
int remove(int val){
    int t=0;
    for(;t<=mg;t++)if(buck[t].val[buck[t].size-1]>=val&&buck[t].val[0]<=val)break;
    for(int i=buck[t].size-1;i>=0;i--){
        if(buck[t].val[i]==val){
            for(int j=i+1;j<buck[t].size;j++){
                buck[t].val[j-1]=buck[t].val[j];
            }
            break;
        }
    }
    buck[t].size--;
    buck[t].upd();
    return buck[t].size;
}
void add(int diff){
    int t=0;
    for(;t<=mg;t++)if(buck[t].val[buck[t].size-1]>=diff)break;
    if(t>mg)t--;
    int idx=upper_bound(buck[t].val,buck[t].val+buck[t].size,diff)-buck[t].val;
    for(int i=buck[t].size;i>idx;i--)buck[t].val[i]=buck[t].val[i-1];
    buck[t].val[idx]=diff;
    buck[t].size++;
    buck[t].upd();
}
int answer(){
    int last=buck[0].last[0];
    int cnt=buck[0].cnt[0];
    for(int g=1;g<=mg;g++){
        if(buck[g].val[buck[g].size-1]<=last)continue;
        int t=upper_bound(buck[g].val,buck[g].val+buck[g].size,last)-buck[g].val;
        cnt+=buck[g].cnt[t];
        last=buck[g].last[t];
    }
    return cnt;
}
void init(int n, int L, int tmp[])
{
    l=L;
    int t=sz;
    for(int i=0;i<n;i++){
        arr[i]=tmp[i];
        if(i==t) t+=sz,mg++;
        cin>>arr[i];
        buck[mg].val[i-t+sz]=arr[i];
        buck[mg].size++;
    }
    for(int i=0;i<=mg;i++){
        buck[mg].upd();
    }
}

int update(int a, int b)
{
    upcnt++;
    if(upcnt==sz) refresh();
    if(!remove(arr[a]))refresh();
    add(b);
    arr[a]=b;
    return answer();
}

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