이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
using namespace std;
#include "elephants.h"
#include <vector>
#include <algorithm>
#define B 400
int n,m,e;
struct bucket{
vector<int> v;
vector<int> z;
vector<int> zz;
bucket(){}
void f(){
z.resize(v.size());
zz.resize(v.size());
int j=v.size()-1;//last in frame
for (int i=v.size()-1;i>=0;i--){
while (v[i]+m<=v[j]){
j--;
}
if (j==(int)v.size()-1){
z[i]=1;
zz[i]=v[i]+m;
}else{
z[i]=z[j+1]+1;
zz[i]=zz[j+1];
}
}
}
int find(int x){
int a,b,y;
a=0;b=v.size();
if (b==0){return 0;}
if (b==1){
if (v[0]>=x){
return 0;
}
return 1;
}
while (a+1!=b){
y=(a+b)/2;
if (v[y]<x){a=y;}
else if (v[y]>x){b=y;}
else{break;}
}
if (v[y]!=x){
if(v[a]<x){y=b;}else{y=a;}
}
return y;
}
};
vector<bucket> v;
int bigfind(int x){
int a,b,y;
a=0;b=v.size();
while (a+1!=b){
y=(a+b)/2;
while (y<b && v[y].v.size()==0){y++;}
while (y>=a && v[y].v.size()==0){y--;}
if ((v[a].v[0]<=x) && (v[y-1].v[v[y-1].v.size()-1]>=x)){b=y;}
else if (v[a].v[0]>=x){b=y;}
else {a=y;}
}
return a;
}
vector<int> w;
void bucketer(){
vector<int> t=w;
sort(t.begin(),t.end());
v.clear();
int i=0;
int k=0;
while (i<n){
v.push_back(bucket());
for (int j=0;j<B;j++){
if (i+j>=n){break;}
v[k].v.push_back(t[i+j]);
}
i+=B;
k++;
}
for (int i=0;i<(int)v.size();i++){
v[i].f();
}
}
void init(int N, int L, int X[]){
n=N;
m=L+1;
e=0;
w.resize(n);
for (int i=0;i<n;i++){w[i]=X[i];}
bucketer();
}
int update(int i, int y){
int x=bigfind(y);
v[x].v.insert(v[x].v.begin()+v[x].find(y),y);
v[x].f();
x=bigfind(w[i]);
v[x].v.erase(v[x].v.begin()+v[x].find(w[i]));
v[x].f();
w[i]=y;
e++;
if (e==B){
bucketer();
e=0;
}
// if (y==0){for (auto vv:v){for(auto vvv:vv.v){print(vvv);}print(-1);}}
int z=0;
x=0;
for (int j=0;j<(int)v.size();j++){
if (v[j].find(x)==v[j].v.size()){continue;}
x=v[j].find(x);//print(v[j].v[x]);
z+=v[j].z[x];//print(z);
x=v[j].zz[x];//print(x);
}
return z;
}
컴파일 시 표준 에러 (stderr) 메시지
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:113:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | if (v[j].find(x)==v[j].v.size()){continue;}
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~
# | 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... |