#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5,MAX=1e9+5;
int n,k,mx,ans,nxt=1,arr[mxn],L[mxn*20],R[mxn*20],loc[mxn],idx[mxn];
ll tree[mxn*20];
multiset<int>st[mxn];
set<int>total;
set<int>camera;
map<int,int>mp;
map<int,int>mp2;
void init(int N, int L, int X[])
{
n=N,k=L;
for(int i=1;i<=n;i++){
arr[i]=X[i-1]+1;
total.insert(arr[i]);
}
loc[1]=arr[1];
st[1].insert(arr[1]);
camera.insert(loc[1]);
mp2[loc[1]]=1;
idx[1]=1;
mp[arr[1]]=1;
mx=1;
for(int i=2;i<=n;i++){
if(arr[i]-loc[mx]>k){
loc[++mx]=arr[i];
idx[i]=mx;
st[mx].insert(arr[i]);
camera.insert(loc[mx]);
mp2[loc[mx]]=mx;
mp[arr[i]]=i;
}
else{
idx[i]=mx;
mp[arr[i]]=i;
st[mx].insert(arr[i]);
}
}
ans=mx;
}
void del(int pos,int val){
st[pos].erase(val);
}
void add(int pos,int val){
st[pos].insert(val);
int id=mp[val];
idx[id]=pos;
}
int update(int i, int y)
{
i++,y++;
st[idx[i]].erase(st[idx[i]].find(arr[i]));
if(st[idx[i]].size()==0){
ans--;
camera.erase(loc[idx[i]]);
}
else if(*st[idx[i]].begin()!=loc[idx[i]]){
camera.erase(loc[idx[i]]);
loc[idx[i]]=*st[idx[i]].begin();
camera.insert(loc[idx[i]]);
mp2[loc[idx[i]]]=idx[i];
}
arr[i]=y;
mp[y]=i;
auto it=camera.upper_bound(arr[i]);
if(it!=camera.begin()){
it--;
int x=*it;
auto it2=camera.upper_bound(x-1);
if(it2!=camera.begin()){
it2--;
int l=*it2,r=x;
int lpos=mp2[l],rpos=mp2[r];
while(st[rpos].size()&&*st[rpos].begin()-l<=k){
int nw=*st[rpos].begin();
del(rpos,nw);
add(lpos,nw);
}
if(st[rpos].size()==0){
camera.erase(r);
ans--;
}
else{
int first=*st[rpos].begin();
if(first!=r){
camera.erase(r);
loc[mp2[r]]=first;
mp2[first]=mp2[r];
camera.insert(first);
}
}
}
it=camera.upper_bound(arr[i]);
it--;
x=*it;
if(arr[i]-x<=k){
add(mp2[x],arr[i]);
return ans;
}
}
it=camera.lower_bound(arr[i]);
if(it!=camera.end()){
int x=*it;
int pos=mp2[x];
int last=*(--st[pos].end());
if(last-arr[i]<=k){
loc[pos]=arr[i];
mp2[arr[i]]=pos;
camera.erase(x);
camera.insert(arr[i]);
add(pos,arr[i]);
return ans;
}
}
ans++;
mx++;
loc[mx]=arr[i];
mp2[loc[mx]]=mx;
camera.insert(arr[i]);
add(mx,arr[i]);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
6 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
6 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Incorrect |
4 ms |
9684 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
6 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Incorrect |
4 ms |
9684 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
6 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Incorrect |
4 ms |
9684 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
6 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Incorrect |
4 ms |
9684 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |