#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]);
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;
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]]++;
}
}
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.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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
436 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
436 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1135 ms |
5772 KB |
Output is correct |
| 8 |
Correct |
1401 ms |
6312 KB |
Output is correct |
| 9 |
Correct |
4499 ms |
9320 KB |
Output is correct |
| 10 |
Correct |
3490 ms |
10052 KB |
Output is correct |
| 11 |
Correct |
2324 ms |
9996 KB |
Output is correct |
| 12 |
Correct |
5096 ms |
10256 KB |
Output is correct |
| 13 |
Correct |
4465 ms |
9768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
436 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1135 ms |
5772 KB |
Output is correct |
| 8 |
Correct |
1401 ms |
6312 KB |
Output is correct |
| 9 |
Correct |
4499 ms |
9320 KB |
Output is correct |
| 10 |
Correct |
3490 ms |
10052 KB |
Output is correct |
| 11 |
Correct |
2324 ms |
9996 KB |
Output is correct |
| 12 |
Correct |
5096 ms |
10256 KB |
Output is correct |
| 13 |
Correct |
4465 ms |
9768 KB |
Output is correct |
| 14 |
Correct |
1596 ms |
6272 KB |
Output is correct |
| 15 |
Correct |
2636 ms |
8044 KB |
Output is correct |
| 16 |
Correct |
6501 ms |
12564 KB |
Output is correct |
| 17 |
Execution timed out |
9051 ms |
14292 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
436 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1135 ms |
5772 KB |
Output is correct |
| 8 |
Correct |
1401 ms |
6312 KB |
Output is correct |
| 9 |
Correct |
4499 ms |
9320 KB |
Output is correct |
| 10 |
Correct |
3490 ms |
10052 KB |
Output is correct |
| 11 |
Correct |
2324 ms |
9996 KB |
Output is correct |
| 12 |
Correct |
5096 ms |
10256 KB |
Output is correct |
| 13 |
Correct |
4465 ms |
9768 KB |
Output is correct |
| 14 |
Correct |
1596 ms |
6272 KB |
Output is correct |
| 15 |
Correct |
2636 ms |
8044 KB |
Output is correct |
| 16 |
Correct |
6501 ms |
12564 KB |
Output is correct |
| 17 |
Execution timed out |
9051 ms |
14292 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
