이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//constants
const int MAXN=150000;
const int blk=400;
//important stuffs
int n,nb,l,cnt,arr[MAXN];
//elephant indices
int ind[MAXN];
//decomposition blocks
int pos[375][2*blk];
int val[375][2*blk];
int dis[375][2*blk];
//block sizes
int si[375];
//actual code
void recalc(int p){
if(si[p]==0)return;
int pnt=si[p];
for(int i=si[p]-1;i>=0;i--){
while(pos[p][pnt-1]-l>pos[p][i])pnt--;
if(pnt==si[p]){
val[p][i]=1;
dis[p][i]=pos[p][i]+l;
}
else{
val[p][i]=val[p][pnt]+1;
dis[p][i]=dis[p][pnt];
}
}
}
void reconstruct(){
int tc=0;
for(int i=0;i<nb;i++){
for(int j=0;j<si[i];j++)arr[tc++]=pos[i][j];
}
for(int i=0;i<nb;i++){
for(int j=0;j<blk&&i*blk+j<n;j++){
pos[i][j]=arr[i*blk+j];
si[i]=j+1;
}
recalc(i);
}
}
void sub(int p,int v){
int tc=0;
while(pos[p][tc]!=v)tc++;
for(int i=tc+1;i<si[p];i++)pos[p][i-1]=pos[p][i];
si[p]--;
}
void add(int p,int v){
int tc=si[p];
while(tc>0&&pos[p][tc-1]>v){
pos[p][tc]=pos[p][tc-1];
tc--;
}
pos[p][tc]=v;
si[p]++;
}
int query(){
int ret=0;
int cp=-1;
for(int i=0;i<nb;i++){
if(si[i]==0||pos[i][si[i]-1]<=cp)continue;
int bp=(int*)lower_bound(pos[i],pos[i]+si[i],cp+1)-pos[i];
ret+=val[i][bp];
cp=dis[i][bp];
}
return ret;
}
void init(int N,int L,int X[]){
n=N;
l=L;
nb=ceil((double)n/blk);
cnt=0;
for(int i=0;i<n;i++)ind[i]=X[i];
for(int i=0;i<nb;i++){
for(int j=0;j<blk&&i*blk+j<n;j++){
pos[i][j]=X[i*blk+j];
si[i]=j+1;
}
recalc(i);
}
}
int update(int i,int y){
cnt++;
if(cnt%blk==0)reconstruct();
int tc=0;
while(si[tc]==0||pos[tc][0]>ind[i]||pos[tc][si[tc]-1]<ind[i])tc++;
sub(tc,ind[i]);
recalc(tc);
tc=0;
int prev=INT_MIN;
while(tc<nb-1&&(si[tc]==0||prev>y||pos[tc][si[tc]-1]<y)){
if(si[tc]!=0)prev=pos[tc][si[tc]-1];
tc++;
}
add(tc,y);
recalc(tc);
ind[i]=y;
return query();
}
void output(){
for(int i=0;i<nb;i++){
for(int y=0;y<si[i];y++)cout<<pos[i][y]<<" ";
cout<<"\n";
}
for(int i=0;i<nb;i++){
for(int y=0;y<si[i];y++)cout<<val[i][y]<<" ";
cout<<"\n";
}
for(int i=0;i<nb;i++){
for(int y=0;y<si[i];y++)cout<<dis[i][y]<<" ";
cout<<"\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |