Submission #252168

#	Time	Username	Problem	Language	Result	Execution time	Memory
252168		guangxuan	Dancing Elephants (IOI11_elephants)	C++14	0 / 100	1 ms	384 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long 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;
vector<ll> ind2coord;
vector<ll> bucketx; //x coords of buckets + INF coord
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]);
    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;
    sizev = sqrt(positions.size());
    bucketx.push_back(-1);
    for (auto p : positions){
        if (len==0){
            bucketx.push_back(p.first);
        }
        len++;
        if (len==sizev){
            len=0;
        }
    }
    bucketx.push_back(INF);
    
    /*for (ll i : bucketx){
        //cout<<i<<", ";
    }//cout<<"\n";*/
 
    for (ll i = bucketx.size()-2; i>=0; i--){
        updateBucket(i);
    }
}
 
void init(int N, int L, int X[]) {
    n = N;l=L;
    ind2coord = vector<ll>(X,X+n);
    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]]++;
        }
    }
  return;
    genBuckets();
}
 
int update(int i, int y) {
    //cout<<"update "<<i<<" "<<y<<'\n';
    //remove thing at index i
  return 0;
    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%sizev==0){
        qcount=0;
        genBuckets();
    } else {
        //cout<<oldplace<<" "<<newplace<<'\n';
        updateBucket(upper_bound(bucketx.begin(),bucketx.end(),oldplace)-bucketx.begin()-1);
        updateBucket(upper_bound(bucketx.begin(),bucketx.end(),newplace)-bucketx.begin()-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: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3