이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define lb(a, x) lower_bound(begin(a), end(a), x)
using namespace std;
constexpr int MX=150000, B=448, C=(MX+B-1)/B;
struct iii { int x, n, y; };
bool operator<(const iii& a, int b) { return a.x<b; }
bool operator<(int a, const iii& b) { return a<b.x; }
int A[MX], X[MX], N, M, Q;
vector<iii> D[C];
void calc_bucket(vector<iii>& v) {
for(int n=v.size(), i=n, p=n; i--;) {
while(p && v[i].x<v[p-1].x-M) p--;
if(p==n) v[i].n=1, v[i].y=v[i].x+M;
else v[i].n=v[p].n+1, v[i].y=v[p].y;
}
}
void init_buckets() {
int k=0;
for(auto&v:D) {
for(auto[x,n,y]:v) X[k++]=x;
v.clear();
}
for(int i=0, j=0; i<N;) {
D[j].push_back({X[i], 0, 0});
if(++i%B==0 || i==N) calc_bucket(D[j++]);
}
}
void del(int x) {
for(auto&v:D) if(v.size() && v.front().x<=x && x<=v.back().x) {
v.erase(lb(v, x));
calc_bucket(v);
break;
}
}
void add(int x) {
int p=0, n=N-1;
for(auto&v:D) if(!(n-=v.size()) || v.size() && p<=x && x<=(p=v.back().x)) {
v.insert(lb(v, x), {x, 0, 0});
calc_bucket(v);
break;
}
}
int answer() {
int p=0, n=0;
for(auto&v:D) if(v.size() && p<=v.back().x) {
auto[x,m,y]=*lb(v, p);
n+=m, p=y+1;
}
return n;
}
void init(int n, int m, int E[]) {
N=n, M=m;
for(int i=0; i<C; i++) D[i].reserve(B);
for(int i=0; i<N; i++) D[i/B].push_back({A[i]=E[i], 0, 0});
}
int update(int n, int x) {
if(Q++%B==0) init_buckets();
del(A[n]);
add(A[n]=x);
return answer();
}
컴파일 시 표준 에러 (stderr) 메시지
elephants.cpp: In function 'void init_buckets()':
elephants.cpp:21:17: warning: unused variable 'n' [-Wunused-variable]
for(auto[x,n,y]:v) X[k++]=x;
^
elephants.cpp:21:17: warning: unused variable 'y' [-Wunused-variable]
elephants.cpp: In function 'void add(int)':
elephants.cpp:38:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
for(auto&v:D) if(!(n-=v.size()) || v.size() && p<=x && x<=(p=v.back().x)) {
~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int answer()':
elephants.cpp:47:13: warning: unused variable 'x' [-Wunused-variable]
auto[x,m,y]=*lb(v, p);
^
# | 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... |