#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int N=150005;
const int K=500;
const int inf=1e9;
int n,L;
int X[N];
struct elephant{
int id,pos,needed,covered;
elephant(){}
elephant(int id,int pos):id(id),pos(pos){}
bool operator<(const elephant &o)const{
return pos<o.pos;
}
}elep[N];
vector<elephant> block[K];
void computeblock(int i){
deque<elephant> dq;
for(int j=block[i].size()-1;j>=0;j--){
if(dq.empty()||block[i][j].pos+L>=dq.back().pos){
block[i][j].needed=1;
block[i][j].covered=block[i][j].pos+L;
}else{
while(dq.size()>1&&dq.end()[-2].pos>block[i][j].pos+L)dq.pop_back();
block[i][j].needed=dq.back().needed+1;
block[i][j].covered=dq.back().covered;
}
dq.emplace_front(block[i][j]);
}
}
void build(){
for(int i=0;i<K;i++)block[i].clear();
for(int i=0;i<n;i++)block[i/K].emplace_back(elep[i]);
for(int i=0;i<K;i++){
computeblock(i);
}
}
void init(int N, int _L, int _X[]){
n=N,L=_L;
for(int i=0;i<n;i++)X[i]=_X[i];
for(int i=0;i<n;i++)elep[i]=elephant(i,X[i]);
build();
}
int findblock(int pos){
int l=0,r=K-1;
while(l<r){
int m=(l+r+1)/2;
if(!block[m].empty()&&block[m][0].pos<=pos)l=m;
else r=m-1;
}
return l;
}
int counter=0;
int update(int i, int y){
if(counter==K){
counter=0;
int id=0;
for(int i=0;i<K;i++)for(auto e:block[i])elep[id++]=e;
}
counter++;
int id=findblock(X[i]);
auto it=block[id].begin();
while(it->id!=i)it++;
auto tmp=*it;
block[id].erase(it);
computeblock(id);
X[i]=y;
tmp.pos=y;
id=findblock(X[i]);
it=block[id].begin();
while(it!=block[id].end()&&it->pos<=X[i])it++;
block[id].insert(it,tmp);
computeblock(id);
int ans=0;
int pos=-inf;
for(int i=0;i<K;i++){
auto it=upper_bound(block[i].begin(),block[i].end(),elephant(-1,pos));
if(it==block[i].end())continue;
ans+=it->needed;
pos=it->covered;
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
592 ms |
1428 KB |
Output is correct |
8 |
Correct |
599 ms |
1620 KB |
Output is correct |
9 |
Correct |
657 ms |
2904 KB |
Output is correct |
10 |
Runtime error |
33 ms |
5844 KB |
Execution killed with signal 11 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
592 ms |
1428 KB |
Output is correct |
8 |
Correct |
599 ms |
1620 KB |
Output is correct |
9 |
Correct |
657 ms |
2904 KB |
Output is correct |
10 |
Runtime error |
33 ms |
5844 KB |
Execution killed with signal 11 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
592 ms |
1428 KB |
Output is correct |
8 |
Correct |
599 ms |
1620 KB |
Output is correct |
9 |
Correct |
657 ms |
2904 KB |
Output is correct |
10 |
Runtime error |
33 ms |
5844 KB |
Execution killed with signal 11 |
11 |
Halted |
0 ms |
0 KB |
- |