이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("-Ofast","-funroll-all-loops","-fno-stack-protector")
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ 305555
int n;
//B块
#define pb push_back
typedef pair<int,int> pii;
#define fi first
#define se second
int B=105,G=0;
vector<int> bl[SZ];
vector<int> seq;
set<pii> ns;
int be[SZ],x[SZ],W,blk[SZ];
int ts[SZ];
int* getseq()
{
int tn=0;
for(auto t:seq)
for(auto u:bl[t]) ts[tn++]=u;
return ts;
}
#define j1 ju1
int j1[SZ];
pii js[SZ];
inline void reset_block(vector<int>&v)
{
int j=0,vn=v.size();
for(int i=0;i<vn;++i)
{
while(j<vn&&x[v[j]]<=x[v[i]]+W) ++j;
if(j==vn) j1[v[i]]=-1;
else j1[v[i]]=v[j];
}
for(int i=int(vn)-1;i>=0;--i)
if(j1[v[i]]==-1) js[v[i]].fi=v[i],js[v[i]].se=0;
else
js[v[i]].fi=js[j1[v[i]]].fi,
js[v[i]].se=js[j1[v[i]]].se+1;
}
inline void rebuild(int*v)
{
int u=int(n)/B;
if(!u) ++u;
for(int i=1;i<=G;++i) bl[i].clear();
seq.clear(); G=0;
vector<int> p; p.reserve(u);
for(int i=0;i<n;++i)
{
p.pb(v[i]);
if(p.size()>=u||i==n-1)
{
bl[++G]=p,reset_block(p);
for(auto t:p) blk[t]=G;
seq.pb(G),p.clear();
p.reserve(u);
}
}
}
inline int ask()
{
int s=ns.begin()->se,cn=0;
while(1)
{
if(js[s].se)
cn+=js[s].se,s=js[s].fi;
auto u=ns.lower_bound(pii(x[s]+W+1,0));
++cn; if(u==ns.end()) break; s=u->se;
}
return cn;
}
int cnt=0;
void init(int N, int L_, int X[])
{
n=N; W=L_;
for(int i=0;i<n;++i) x[i]=X[i];
vector<int> v;
for(int i=0;i<n;++i)
v.pb(i),ns.insert(pii(x[i],i));
rebuild(v.data());
}
int update(int t,int y)
{
ns.erase(pii(x[t],t));
{
int i=blk[t];
vector<int>&B=bl[i];
for(int j=0;;++j)
if(B[j]==t) {B.erase(B.begin()+j); break;}
if(B.size()) reset_block(B);
else
{
for(int j=0;;++j)
if(seq[j]==i) {seq.erase(seq.begin()+j); break;}
}
}
x[t]=y; ns.insert(pii(x[t],t));
for(int i=0;i<int(seq.size());++i)
if(x[t]<=x[bl[seq[i]].back()]||i+1==int(seq.size()))
{
static int us[SZ]; int un=0;
vector<int> &s=bl[seq[i]]; bool c=0;
for(int j=0;j<s.size();++j)
{
if(x[s[j]]>x[t])
{if(!c) us[un++]=t; c=1;}
us[un++]=s[j];
}
if(!c) us[un++]=t; s.pb(0);
for(int i=0;i<un;++i) s[i]=us[i];
reset_block(s); blk[t]=seq[i];
break;
}
++cnt;
if(cnt%(B*4)==0) rebuild(getseq());
return ask();
}
컴파일 시 표준 에러 (stderr) 메시지
elephants.cpp: In function 'void rebuild(int*)':
elephants.cpp:53:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(p.size()>=u||i==n-1)
~~~~~~~~^~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:105:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<s.size();++j)
~^~~~~~~~~
elephants.cpp:111:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(!c) us[un++]=t; s.pb(0);
^~
elephants.cpp:111:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(!c) us[un++]=t; s.pb(0);
^
# | 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... |