Submission #815166

#	Time	Username	Problem	Language	Result	Execution time	Memory
815166		annabeth9680	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	12 ms	3256 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int B = 500;
const int U = 400;
int sizes[305],l,n,curq,num;
int a[150005],b[150005];
struct el{
    int val;
    int nxt;
    int cnt;
}buckets[305][905];
bool operator<(el x, el y){
    return x.val < y.val;
}
void blable(int bi){
    int p = sizes[bi];
    for(int i = sizes[bi]-1;i>=0;--i){
        while(p > 0 && buckets[bi][p-1].val > buckets[bi][i].val+l){
            p--;
        }
        if(p == sizes[bi]){
            buckets[bi][i].nxt = -1;
            buckets[bi][i].cnt = 0;
        }
        else{
            if(buckets[bi][p].nxt == -1){
                buckets[bi][i].nxt = p;
            }
            else{
                buckets[bi][i].nxt = buckets[bi][p].nxt;
            }
            buckets[bi][i].cnt = buckets[bi][p].cnt+1;
        }
    }
}
void bclear(){
    int c = 0;
    for(int i = 0;i<num;++i){
        for(int j = 0;j<sizes[i];++j){
            b[c++] = buckets[i][j].val;
        }
    }
    for(int i = 0;i<num;++i){
        sizes[i] = min(B,n-i*B);
        for(int j = 0;j<sizes[i];++j){
            buckets[i][j].val = b[i*B+j];
        }
        blable(i);
    }
}
void bupdate(int pos, int bi, int v){
    sizes[bi]++;
    for(int i = sizes[bi]-1;i>pos;i--){
        buckets[bi][i] = buckets[bi][i-1];
    }
    buckets[bi][pos].val = v;
    blable(bi);
}
void berase(int bi, int pos){
    sizes[bi]--;
    for(int i = pos;i<sizes[bi];++i){
        buckets[bi][i] = buckets[bi][i+1];
    }
    blable(bi);
}
void init(int N, int L, int X[]){
    n = N; l = L;
    memcpy(a,X,sizeof(a)); memcpy(b,X,sizeof(b));
    while(num*B < N){
        num++;
    }
    bclear();
}
int query(){
    int ans = 0, pos = 0;
    for(int i = 0;i<num;){ //don't add 1 to i yet, it depends on how we calculate it
        if(sizes[i] == 0){
            i++;
            continue;
        }
        ans += buckets[i][pos].cnt+1;
        if(buckets[i][pos].nxt != -1) pos = buckets[i][pos].nxt;
        int posval = buckets[i][pos].val+l+1, ind = i+1;
        while(true){
            if(ind == num) break;
            if(lower_bound(buckets[ind],buckets[ind]+sizes[ind],(el){posval,0,0}) != buckets[ind]+sizes[ind]) break;
            ind++;
        }
        if(ind == num) break;
        i = ind;
        pos = (int)(lower_bound(buckets[i],buckets[i]+sizes[i],(el){posval,0,0}) - buckets[i]);
    }
    return ans;
}
int update(int pos, int y){ //first erase the previous element, update the new one, then query
    curq = (curq+1)%U;
    int x = a[pos]; a[pos] = y;
    for(int i = 0;i<num;++i){
        if(sizes[i] == 0) continue;
        if(buckets[i][0].val <= x && x <= buckets[i][sizes[i]-1].val){
            int it = (int)(lower_bound(buckets[i],buckets[i]+sizes[i],(el){x,0,0})-buckets[i]);
            berase(i,it);
        }
    }
    int f = -1;
    for(int i = 0;i<num;++i){
        if(buckets[i][0].val <= y){
            f = i;
            break;
        }
    }
    if(f == -1){
        bupdate(0,0,y);
    }
    else{
        int it = (int)(lower_bound(buckets[f],buckets[f]+sizes[f],(el){y,0,0})-buckets[f]);
        bupdate(it,f,y);
    }
    if(curq == 0) bclear();
    return query();
}

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