Submission #254978

#	Time	Username	Problem	Language	Result	Execution time	Memory
254978		eohomegrownapps	Dancing Elephants (IOI11_elephants)	C++14	50 / 100	9068 ms	14028 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,l;

map<ll,pair<ll,ll>> positions; //{position, {nextpos, bucketstart}}
//num cameras to protrude outside bucket, right coord of bucketwidth
unordered_map<ll,ll> poscnt;
ll ind2coord[100000];
ll bucketx[100000]; //x coords of buckets + INF coord
int bsp=0;
ll INF = 1e9+1;
//denotes end of sequence
ll sizev;
ll qcount = 0;
void updateBucket(int ind){
    //cout<<"updating "<<ind<<" "<<bucketx[ind]<<'\n';
    //generate bucketstart, numcameras, nextpos from positions
    auto it = positions.lower_bound(bucketx[ind+1]);
    if (it==positions.begin()){return;}
    ll ptr = ind;
    do {
        it = prev(it);
        //cout<<it->first<<'\n';
        //process
        if (it->first<bucketx[ptr]){
            return;
        }
        ll rightedge = it->first+l; //upper_bound
        if (rightedge<bucketx[ptr+1]){
            auto ub = positions.upper_bound(rightedge);
            if (ub==positions.end()){
                (it->second).first = 1;
                (it->second).second = INF;
            } else if (ub->first>=bucketx[ptr+1]){
                (it->second).first = 1;
                (it->second).second = rightedge;
            } else {
                (it->second).first = (ub->second).first+1;
                (it->second).second = (ub->second).second;
            }
        } else {
            (it->second).first = 1;
            (it->second).second = rightedge;
        }
    } while (it!=positions.begin());
    //assert(ind==0||0==1);
}

void genBuckets(){
    //cout<<"generating\n";
    //bucketx.clear();
    ll len = 0;
    //bucketx.push_back(-1);
    bsp=0;
    bucketx[bsp]=-1;
    bsp++;
    for (auto p : positions){
        if (len==0){
            bucketx[bsp]=p.first;
            bsp++;
        }
        len++;
        if (len==sizev){
            len=0;
        }
    }
    bucketx[bsp]=INF;
    bsp++;
    
    /*for (ll i : bucketx){
        //cout<<i<<", ";
    }//cout<<"\n";*/

    for (ll i = bsp-2; i>=0; i--){
        updateBucket(i);
    }
}

void init(int N, int L, int X[]) {
    n = N;l=L;
    for (int i = 0; i<n; i++){
        ind2coord[i]=X[i];
    }
    for (ll i = 0; i<n; i++){
        if (poscnt.find(X[i])==poscnt.end()){
            poscnt[X[i]]++;
            positions[X[i]]={INF,INF};
        } else {
            poscnt[X[i]]++;
        }
    }
    sizev = sqrt(positions.size());
    genBuckets();
}

int update(int i, int y) {
    //cout<<"update "<<i<<" "<<y<<'\n';
    //remove thing at index i
    ll oldplace = ind2coord[i];
    ind2coord[i]=y;
    ll newplace = y;
    poscnt[oldplace]--;
    if (poscnt[oldplace]==0){
        positions.erase(oldplace);
    }
    if (poscnt[newplace]==0){
        positions[newplace]={INF,INF};
    }
    poscnt[newplace]++;
    qcount++;
    if (qcount%1000==0){
        qcount=0;
        genBuckets();
    } else {
        //cout<<oldplace<<" "<<newplace<<'\n';
        updateBucket(upper_bound(bucketx,bucketx+bsp,oldplace)-bucketx-1);
        updateBucket(upper_bound(bucketx,bucketx+bsp,newplace)-bucketx-1);
    }
    ll cnt = 0;
    auto ptr = positions.begin();
    while (ptr!=positions.end()){
        cnt+=ptr->second.first;
        ptr = positions.upper_bound(ptr->second.second);
    }
    assert(cnt<INF);
    return cnt;
}

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