| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 254982 | eohomegrownapps | Dancing Elephants (IOI11_elephants) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = min(max(sqrt(positions.size(),50),sqrt(positions.size())/2);
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%sizev==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;
}