| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 198277 | red1108 | Dancing Elephants (IOI11_elephants) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define eb emplace_back
int n, L, q, siz=400, num;
vector<int> b[410];
int dp[410][810], rem[410][810];
int pos[150010], ans;
vector<int> help;
void gang(int ind){
if(!b[ind].empty()){
int si = b[ind].size(), r = si-1;
for(int i=si-1;i>=0;i--){
while(b[ind][r]-b[ind][i]>L) r--;
if(r+1==si){
dp[ind][i] = 1;
rem[ind][i]=b[ind][i]+L;
}
else{
dp[ind][i] = dp[ind][r+1]+1;
rem[ind][i] = rem[ind][r+1];
}
}
}
ans=0;
int l = -1;
for(int i=1;i<=num;i++){
if(b[i].empty()) continue;
int t = upper_bound(b[i].begin(), b[i].end(), l)-b[i].begin();
if(t==b[i].size()) continue;
ans = ans + dp[i][t];
l = rem[i][t];
}
}
void del(int x){
int ind=-1;
for(int i=1;i<=num;i++){
if(b[i].empty()) continue;
if(b[i][0]>x){ind = (ind==-1?i:ind);break;}
ind = i;
}
b[ind].erase(lower_bound(b[ind].begin(), b[ind].end(), x));
gang(ind);
}
void add(int x){
int ind=-1;
for(int i=1;i<=num;i++){
if(b[i].empty()) continue;
if(b[i][0]>x){ind = (ind==-1?i:ind);break;}
ind = i;
}
b[ind].insert(upper_bound(b[ind].begin(), b[ind].end(), x), x);
gang(ind);
}
void reset(){
help.clear();
for(int i=1;i<=n;i++) help.eb(pos[i]);
sort(help.begin(), help.end());
for(int i=1;i<=num;i++) b[i].clear();
for(int i=0;i<help.size();i++) b[i/siz+1].eb(help[i]);
for(int i=1;i<=num;i++) gang(i);
}
int main(){
fastio;
cin>>n>>L>>q;
for(int i=1;i<=n;i++) cin>>pos[i];
num = n/siz;
if(n%siz) num++;
for(int i=0;i<q;i++){
if(i%siz==0) reset();
int a, p;
cin>>a>>p;a++;
del(pos[a]);
pos[a]=p;
add(pos[a]);
cout<<ans<<"\n";
}
}