| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 312473 | knon0501 | 코끼리 (Dancing Elephants) (IOI11_elephants) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int t=400;
int n,L,m;
int b[150000];
int c[150000];
struct A{
int x,cnt,nxt,idx;
};
vector<A> a[400];
void init(){
int i,j;
for(i=0 ; i<n ; i++)c[i]=b[i];
sort(c,c+n);
for(i=0 ; i<n ;i++)
a[i/t].push_back({c[i],0,0});
for(i=(n-1)/t ; i>=0 ; i--){
for(j=(int)a[i].size()-1 ; j>=0 ; j--){
if(a[i][j].x+L>=a[i].rbegin()->x){
a[i][j].nxt=a[i][j].x+L;
a[i][j].cnt=1;
}
else{
auto k=upper_bound(a[i].begin(),a[i].end(),(A){a[i][j].x+L,0,0},[&](A q,A w){
return q.x<w.x;
});
a[i][j].cnt=k->cnt+1;
a[i][j].nxt=k->nxt;
}
}
}
}
void del(int x,int y){
for(int i=0 ; i<a[x].size() ; i++){
if(a[x][i].x==y){
a[x].erase(a[x].begin()+i);
break;
}
}
for(int i=(int)a[x].size()-1 ; i>=0 ; i--){
if(a[x][i].x+L>=a[x].rbegin()->x){
a[x][i].nxt=a[x][i].x+L;
a[x][i].cnt=1;
}
else{
auto k=upper_bound(a[x].begin(),a[x].end(),(A){a[x][i].x+L,0,0},[&](A q,A w){
return q.x<w.x;
});
a[x][i].cnt=k->cnt+1;
a[x][i].nxt=k->nxt;
}
}
}
void add(int x,int y){
for(int i=0 ; i<=a[x].size() ; i++){
if(i==a[x].size() || a[x][i].x>=y ){
a[x].insert(a[x].begin()+i,{y,0,0});
break;
}
}
for(int i=(int)a[x].size()-1 ; i>=0 ; i--){
if(a[x][i].x+L>=a[x].rbegin()->x){
a[x][i].nxt=a[x][i].x+L;
a[x][i].cnt=1;
}
else{
auto k=upper_bound(a[x].begin(),a[x].end(),(A){a[x][i].x+L,0,0},[&](A q,A w){
return q.x<w.x;
});
a[x][i].cnt=k->cnt+1;
a[x][i].nxt=k->nxt;
}
/// cout<<a[x][i].x<<" "<<a[x][i].nxt<<" "<<a[x][i].cnt<<endl;
}
}
int f(){
int x=-2e9;
int ans=0;
for(int i=0 ; i<=(n-1)/t ; i++){
if(a[i].size()==0 || x>a[i].rbegin()->x)continue;
auto k=upper_bound(a[i].begin(),a[i].end(),(A){x,0,0},[&](A q, A w){
return q.x<w.x;
});
ans+=k->cnt;
x=k->nxt;
}
return ans;
}
int g(int x){
int k=-1;
for(int i=0 ; i<=(n-1)/t ; i++){
if(x<=a[i].rbegin()->x)k=i;
}
if(k>=0)return k;
return (n-1)/t;
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>L>>m;
int i;
for(i=0 ; i<n ; i++)cin>>b[i];
for(i=0 ; i<m ; i++)
{
if(i%(t-1)==0)init();
int x,y;
cin>>x>>y;
del(g(b[x]),b[x]);
add(g(y),y);
b[x]=y;
cout<<f()<<"\n";
}
return 0;
}