#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=100,G=0;
vector<int> bl[SZ];
vector<int> seq;
set<pii> ns;
int be[SZ],x[SZ],W,blk[SZ];
vector<int> getseq()
{
vector<int> v; v.reserve(n);
for(auto t:seq)
for(auto u:bl[t]) v.pb(u);
return v;
}
#define j1 ju1
int j1[SZ];
pii js[SZ];
inline void reset_block(vector<int>&v)
{
int j=0;
for(int i=0;i<v.size();++i)
{
while(j<v.size()&&x[v[j]]<=x[v[i]]+W) ++j;
if(j==v.size()) j1[v[i]]=-1;
else j1[v[i]]=v[j];
}
for(int i=int(v.size())-1;i>=0;--i)
if(j1[v[i]]==-1) js[v[i]]=pii(v[i],0);
else js[v[i]]=pii(
js[j1[v[i]]].fi,js[j1[v[i]]].se+1);
}
inline void rebuild(const vector<int>& v)
{
int u=int(v.size())/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<int(v.size());++i)
{
p.pb(v[i]);
if(p.size()>=u||i+1==int(v.size()))
{
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;
inline 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);
}
inline int update(int t,int y)
{
ns.erase(pii(x[t],t));
{
int i=blk[t];
vector<int>&B=bl[i];
B.erase(find(B.begin(),B.end(),t));
if(B.size()) reset_block(B);
else seq.erase(find(seq.begin(),seq.end(),i));
}
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()))
{
vector<int> u,&s=bl[seq[i]];
u.reserve(s.size()); bool c=0;
for(int j=0;j<s.size();++j)
{
if(x[s[j]]>x[t])
{if(!c) u.pb(t); c=1;}
u.pb(s[j]);
}
if(!c) u.pb(t);
s=u; reset_block(s); blk[t]=seq[i];
break;
}
++cnt;
if(cnt%(B+B)==0) rebuild(getseq());
return ask();
}
Compilation message
elephants.cpp: In function 'void reset_block(std::vector<int>&)':
elephants.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();++i)
~^~~~~~~~~
elephants.cpp:31:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j<v.size()&&x[v[j]]<=x[v[i]]+W) ++j;
~^~~~~~~~~
elephants.cpp:32:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j==v.size()) j1[v[i]]=-1;
~^~~~~~~~~~
elephants.cpp: In function 'void rebuild(const std::vector<int>&)':
elephants.cpp:50:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(p.size()>=u||i+1==int(v.size()))
~~~~~~~~^~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:97:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<s.size();++j)
~^~~~~~~~~
/tmp/ccMGfIzr.o: In function `main':
grader.cpp:(.text.startup+0x1d): undefined reference to `init(int, int, int*)'
grader.cpp:(.text.startup+0x3f): undefined reference to `update(int, int)'
collect2: error: ld returned 1 exit status
