#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
int n,l,m,a[150005],e[150005],s[150005],ind,en,k,y,tt,ne,here[200005];
set<pair<int,int> > st[150005];
pair<int,int>b[150005],x,dp[200005];
set<pair<int,int> >::iterator it,it1;
inline void update(int f){
if(!st[f].size())return;
it = st[f].end();
it--;
e[f] = (*it).f;
it++;
s[f] = (*st[f].begin()).f;
while(true){
it--;
x = (*it);
if(x.f + l >= e[f])dp[x.s] = mp(1 , x.f + l);
else {
it1 = st[f].upper_bound(mp(x.f + l + 1, 0));
dp[x.s] = dp[(*it1).s];
dp[x.s].f++;
}
if(it == st[f].begin())break;
}
}
inline void build(){
for(int i=1; i<=k; i++)
st[i].clear();
for(int i=1; i<=n; i++)
b[i] = make_pair(a[i] , i);
sort(b + 1, b + n + 1);
for(int i=1; i<=n; i+=k){
s[i] = b[i].f;
int pp = min(n , i + k - 1);
e[i] = b[pp].f;
for(int j=i; j<=pp; j++){
st[i/k+1].insert(b[j]);
here[b[j].s] = i/k+1;
}
}
for(int i=1; i<=k; i++)update(i);
}
inline int solve(){
y = -1;
int ans = 0;
for(int i=1; i<=k; i++){
if(st[i].size() == 0)continue;
if(y >= e[i])continue;
it = st[i].upper_bound(mp(y + 1, 0));
ans += dp[(*it).s].f;
y = dp[(*it).s].s;
}
return ans;
}
int main(){
cin >> n >> l >> m;
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
k = 300;
while(m--){
if(tt % k == 0)build();
tt++;
scanf("%d%d",&ind,&ne);
ind++;
st[here[ind]].erase(st[here[ind]].find(mp(a[ind] , ind)));
update(here[ind]);int o = 0,pp;
for(int i=1; i<=n/k+1; i++)
if(ne <= s[i]){
o = 1;
i = max(i - 1 , 1);
st[i].insert(mp(ne , ind));
here[ind] = i;
update(i);
break;
}
else if(st[i].size())pp = i;
if(!o){
st[pp].insert(mp(ne , ind));
here[ind] = pp;
update(pp);
}
a[ind] = ne;
printf("%d\n",solve());
}
return 0;
}
Compilation message
elephants.cpp: In function 'int main()':
elephants.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
elephants.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&ind,&ne);
~~~~~^~~~~~~~~~~~~~~~~
elephants.cpp:75:37: warning: 'pp' may be used uninitialized in this function [-Wmaybe-uninitialized]
update(here[ind]);int o = 0,pp;
^~
/tmp/cc4SFUy8.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccLIKbKT.o:elephants.cpp:(.text.startup+0x0): first defined here
/tmp/cc4SFUy8.o: In function `main':
grader.cpp:(.text.startup+0x1d): undefined reference to `init(int, int, int*)'
grader.cpp:(.text.startup+0x3f): undefined reference to `update(int, int)'
collect2: error: ld returned 1 exit status
