이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
const int Na=150006;
const int Nq=400;
int n,m,Ms,l,Updcnt,A[Na];
int Lmax[Nq][3*Nq];
int Llen[Nq][3*Nq];
vector < int > v[Nq];
void process_block(int x) {
int r=v[x].size()-1,rmax=v[x][v[x].size()-1];
for (int i=v[x].size()-1; i>=0; i--) {
int pos=v[x][i];
if (pos+l>=v[x][r]) {
Lmax[x][i]=pos+l;
Llen[x][i]=1;
}
else {
while (0<r && pos+l<v[x][r-1])
r--;
Lmax[x][i]=Lmax[x][r];
Llen[x][i]=Llen[x][r]+1;
}
}
}
int get_ans() {
int res=0,cur_block=0;
while (cur_block<Ms && !v[cur_block].size())
cur_block++;
int pos=v[cur_block][0],idx=0;
while (cur_block<Ms) {
int Lmx=Lmax[cur_block][idx];
res+=Llen[cur_block][idx];
while (cur_block<Ms) {
cur_block++;
if (!v[cur_block].size()) continue;
if (Lmx<v[cur_block][v[cur_block].size()-1]) {
int l=0,r=v[cur_block].size()-1,mid;
while (l<=r) {
mid=(l+r)/2;
if (Lmx<v[cur_block][mid]) { idx=mid; r=mid-1; }
else l=mid+1;
}
break;
}
}
}
return res;
}
void restart() {
vector < int > h;
for (int i=0; i<Ms; i++) {
for (int j=0; j<v[i].size(); j++)
h.push_back(v[i][j]);
v[i].clear();
}
for (int i=0; i<h.size(); i++)
v[i/m].push_back(h[i]);
for (int i=0; i<Ms; i++)
process_block(i);
}
void del(int x) {
int cur_block=-1;
while (cur_block<Ms) {
cur_block++;
if (!v[cur_block].size()) continue;
if (v[cur_block][v[cur_block].size()-1]<x) continue;
for (int j=0; j<v[cur_block].size(); j++)
if (v[cur_block][j]==x) {
v[cur_block].erase(v[cur_block].begin()+j);
break;
}
break;
}
process_block(cur_block);
}
void ins(int x) {
int cur_block=-1;
while (cur_block<Ms) {
cur_block++;
if (!v[cur_block].size()) continue;
if (v[cur_block][v[cur_block].size()-1]<=x) continue;
for (int j=0; j<v[cur_block].size(); j++)
if (x<v[cur_block][j]) {
v[cur_block].insert(v[cur_block].begin()+j,x);
break;
}
break;
}
if (cur_block==Ms) {
cur_block--;
v[cur_block].push_back(x);
}
process_block(cur_block);
}
int update(int id, int nv) {
del(A[id]);
A[id]=nv;
ins(A[id]);
Updcnt++;
if (!(Updcnt%m)) restart();
return get_ans();
}
void init(int nn, int ll, int xs[]) {
n=nn,l=ll;
m=sqrt(n);
m+=(m*m!=n);
Ms=(n+m-1)/m;
for (int i=0; i<n; i++) {
A[i]=xs[i];
v[i/m].push_back(A[i]);
}
for (int i=0; i<Ms; i++)
process_block(i);
return;
}
컴파일 시 표준 에러 (stderr) 메시지
elephants.cpp: In function 'void process_block(int)':
elephants.cpp:17:22: warning: unused variable 'rmax' [-Wunused-variable]
int r=v[x].size()-1,rmax=v[x][v[x].size()-1];
^~~~
elephants.cpp: In function 'int get_ans()':
elephants.cpp:40:6: warning: unused variable 'pos' [-Wunused-variable]
int pos=v[cur_block][0],idx=0;
^~~
elephants.cpp: In function 'void restart()':
elephants.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<v[i].size(); j++)
~^~~~~~~~~~~~
elephants.cpp:71:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int j=0; j<v[i].size(); j++)
^~~
elephants.cpp:73:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
v[i].clear();
^
elephants.cpp:76:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<h.size(); i++)
~^~~~~~~~~
elephants.cpp: In function 'void del(int)':
elephants.cpp:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<v[cur_block].size(); j++)
~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void ins(int)':
elephants.cpp:111:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<v[cur_block].size(); j++)
~^~~~~~~~~~~~~~~~~~~~
# | 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... |