#include<bits/stdc++.h>
using namespace std;
const int len=400,maxn=150005,maxg=400;
int n,m,L,id,dest,teamn,x[maxn],belong[maxn],dp[maxn],nxt[maxn],rp[maxg],cnt[maxg];
set<pair<int,int> > S;
void build(){
teamn=0;
pair<int,int> lst;
for(auto p=S.begin();(p++)!=S.end();p++){
p--;
pair<int,int> j=(*p);
int i=j.second;
if(cnt[teamn]>maxg&&j.first!=lst.first){
rp[belong[lst.second]]=x[i];
teamn++;
}
cnt[teamn]++;
belong[i]=teamn;
lst=j;
}
//printf(":)");
rp[teamn]=x[(*(S.rbegin()--)).second];
teamn++;
for(auto p=S.rbegin();p!=S.rend();p++){
if(p==S.rbegin()) continue;
int i=(*p).second;
//printf("(%d)",i);
if(x[i]+L>=rp[belong[i]]){
dp[i]=1;
nxt[i]=(*S.upper_bound(make_pair(x[i]+L,n))).second;
}
else{
int nxtp=(*S.upper_bound(make_pair(x[i]+L,n))).second;
dp[i]=dp[nxtp]+1;
nxt[i]=nxt[nxtp];
}
}
}
int main(){
scanf("%d%d%d",&n,&L,&m);
for(int i=0;i<n;i++){
scanf("%d",&x[i]);
S.insert(make_pair(x[i],i));
}
S.insert(make_pair(2e9+5,n));
build();
while(m--){
scanf("%d%d",&id,&dest);
int bl1=belong[id];
S.erase(make_pair(x[id],id));
cnt[belong[id]]--;
x[id]=dest;
S.insert(make_pair(x[id],id));
int belonging=upper_bound(rp,rp+teamn,x[id])-rp;
if(belonging>=teamn){
belonging=teamn-1;
rp[belonging]=x[id];
}
belong[id]=belonging;
cnt[belong[id]]++;
if(cnt[belong[id]]>2*maxg) build();
else{
for(auto p=S.upper_bound(make_pair(rp[bl1],0));p!=S.lower_bound(make_pair((bl1==0)?0:rp[bl1-1]+1,0));p--){
if(p==S.upper_bound(make_pair(rp[bl1],0))) continue;
int i=(*p).second;
if(x[i]+L>=rp[belong[i]]){
dp[i]=1;
nxt[i]=(*S.upper_bound(make_pair(x[i]+L,n))).second;
}
else{
int nxtp=(*S.upper_bound(make_pair(x[i]+L,n))).second;
dp[i]=dp[nxtp]+1;
nxt[i]=nxt[nxtp];
}
}
auto r=S.lower_bound(make_pair((bl1==0)?0:rp[bl1-1]+1,0));
int l=(*r).second;
if(x[l]+L>=rp[belong[l]]){
dp[l]=1;
nxt[l]=(*S.upper_bound(make_pair(x[l]+L,n))).second;
}
else{
int nxtp=(*S.upper_bound(make_pair(x[l]+L,n))).second;
dp[l]=dp[nxtp]+1;
nxt[l]=nxt[nxtp];
}
bl1=belong[id];
for(auto p=S.upper_bound(make_pair(rp[bl1],0));p!=S.lower_bound(make_pair((bl1==0)?0:rp[bl1-1]+1,0));p--){
if(p==S.upper_bound(make_pair(rp[bl1],0))) continue;
int i=(*p).second;
if(x[i]+L>=rp[belong[i]]){
dp[i]=1;
nxt[i]=(*S.upper_bound(make_pair(x[i]+L,n))).second;
}
else{
int nxtp=(*S.upper_bound(make_pair(x[i]+L,n))).second;
dp[i]=dp[nxtp]+1;
nxt[i]=nxt[nxtp];
}
}
auto q=S.lower_bound(make_pair((bl1==0)?0:rp[bl1-1]+1,0));
int j=(*q).second;
if(x[j]+L>=rp[belong[j]]){
dp[j]=1;
nxt[j]=(*S.upper_bound(make_pair(x[j]+L,n))).second;
}
else{
int nxtp=(*S.upper_bound(make_pair(x[j]+L,n))).second;
dp[j]=dp[nxtp]+1;
nxt[j]=nxt[nxtp];
}
}
int pos=(*S.begin()).second,ans=0;
while(pos<((*S.rbegin()).second)){
ans+=dp[pos];
pos=nxt[pos];
}
printf("%d\n",ans);
}
return 0;
}
Compilation message
elephants.cpp: In function 'int main()':
elephants.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d%d%d",&n,&L,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~~
elephants.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | scanf("%d",&x[i]);
| ~~~~~^~~~~~~~~~~~
elephants.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%d%d",&id,&dest);
| ~~~~~^~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc8CcaOf.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccgT3ali.o:elephants.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc8CcaOf.o: in function `main':
grader.cpp:(.text.startup+0x27): undefined reference to `init(int, int, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x56): undefined reference to `update(int, int)'
collect2: error: ld returned 1 exit status
