Submission #94049

#	Time	Username	Problem	Language	Result	Execution time	Memory
94049		fjzzq2002	Dancing Elephants (IOI11_elephants)	C++14	97 / 100	9025 ms	21900 KiB

elephants

#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=150,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(int j=0;j<bl[t].size();++j)
			ts[tn++]=bl[t][j];
	return ts;
}
#define j1 ju1
int j1[SZ];
pii js[SZ];
inline void reset_block(vector<int>&v_)
{
	int j=0,vn=v_.size(),*v=v_.data();
	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)
			{
				for(int k=j;k+1<B.size();++k)
					B[k]=B[k+1];
				B.pop_back(); break;
			}
		if(B.size()) reset_block(B);
		else
		{
			for(int j=0;;++j)
				if(seq[j]==i)
				{
					for(int k=j;k+1<seq.size();++k)
						seq[k]=seq[k+1];
					seq.pop_back(); 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()))
		{
			while(x[bl[seq[i]].back()]<=x[t]
			&&i+1!=int(seq.size())&&rand()%3) ++i;
			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*3)==0) rebuild(getseq());
	return ask();
}

Compilation message (stderr)

elephants.cpp: In function 'int* getseq()':
elephants.cpp:21:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<bl[t].size();++j)
               ~^~~~~~~~~~~~~
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:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=j;k+1<B.size();++k)
                 ~~~^~~~~~~~~
elephants.cpp:103:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k=j;k+1<seq.size();++k)
                  ~~~^~~~~~~~~~~
elephants.cpp:117:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<s.size();++j)
                ~^~~~~~~~~
elephants.cpp:123:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(!c) us[un++]=t; s.pb(0);
    ^~
elephants.cpp:123: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);
                       ^

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 0 / 3