Submission #123802

#	Time	Username	Problem	Language	Result	Execution time	Memory
123802		baluteshih	Dancing Elephants (IOI11_elephants)	C++14	97 / 100	4764 ms	23368 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
#define MP make_pair
#define F first
#define S second
#define pb push_back
#define MEM(i,j) memset(i,j,sizeof i)
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct mode
{
	int p,dp,out,i;
	list<int>::iterator bln;
};

const int B=400,block_num=200000;
int n,Len;
vector<mode> block[block_num];
vector<mode>::iterator pl[1500005];
queue<int> q;
list<int> ls;

void print()
{
	return;
	int cnt=0;
	for(auto p=ls.begin();p!=ls.end();++p)
	{
		cout << "Block " << ++cnt << "\n";
		for(auto i:block[*p])
			cout << "{" << i.p << "," << i.dp << "," << i.out << "} ";
		ET; 
	}
	ET;
}

int nwblock()
{
	int x=q.front();
	return q.pop(),x;
}

void merge(int i,int j)//j into i
{
	vector<mode> tmp;
	for(int a=0,b=0;a<block[i].size()||b<block[j].size();)
		if(a<block[i].size()&&(b==block[i].size()||block[i][a].p<block[j][b].p))
			tmp.pb(block[i][a++]);
		else
			tmp.pb(block[j][b++]);
	tmp.swap(block[i]),vector<mode>().swap(block[j]),q.push(j);
}

void rebuild(list<int>::iterator it)
{
	if(block[*it].size()>2*B)
	{
		ls.insert(it,nwblock());
		while(block[*it].size()>B)
			block[*prev(it)].pb(block[*it].back()),block[*it].pop_back();
		reverse(ALL(block[*prev(it)])),swap(*it,*prev(it));
		rebuild(it),rebuild(prev(it));
		return;
	}
	if(block[*it].size()*2<B&&next(it)!=ls.end())
	{
		merge(*it,*next(it)),ls.erase(next(it)),rebuild(it);
		return;
	}
	for(int i=block[*it].size()-1,j=block[*it].size();i>=0;--i)
	{
		while(j>0&&block[*it][j-1].p>block[*it][i].p+Len) --j;
		if(j==block[*it].size())
			block[*it][i].dp=1,block[*it][i].out=block[*it][i].p+Len;
		else
			block[*it][i].dp=block[*it][j].dp+1,block[*it][i].out=block[*it][j].out;
		block[*it][i].bln=it,pl[block[*it][i].i]=block[*it].begin()+i;
	}
}

void init(int N, int L, int X[])
{
	Len=L;
	for(int i=0;i<block_num;++i)
		q.push(i);
	int nw=-1;
	for(int i=0;i<N;++i)
	{
		if(!~nw||block[nw].size()==B)
			nw=nwblock(),ls.pb(nw);
		block[nw].pb(mode{X[i],0,0,i,--ls.end()});
	}
	for(auto p=ls.begin();p!=ls.end();++p)
		rebuild(p);
	print();
}

bool yee(int a,mode x)
{
	return a<x.p;
}

int answer()
{
	int nw=-1,ans=0;
	for(auto p=ls.begin();p!=ls.end();++p)
	{
		auto t=upper_bound(ALL(block[*p]),nw,yee);
		if(t!=block[*p].end())
			ans+=t->dp,nw=t->out;
	}
	return ans;
}

int update(int i, int y)
{
	auto it=pl[i]->bln;
	block[*it].erase(pl[i]),rebuild(it);
	if(y>block[*--ls.end()].back().p)
		block[*--ls.end()].pb(mode{y,0,0,i,--ls.end()}),rebuild(--ls.end());
	else
		for(auto p=ls.begin();p!=ls.end();++p)
		{
			if(block[*p].back().p<y) continue;
			block[*p].pb(mode{y,0,0,i,p});
			for(int i=block[*p].size()-1;i>0;--i)
				if(block[*p][i].p<block[*p][i-1].p)
					swap(block[*p][i],block[*p][i-1]);
				else break;
			rebuild(p);
			break;
		}
	print();
	return answer();
}

Compilation message (stderr)

elephants.cpp: In function 'void merge(int, int)':
elephants.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int a=0,b=0;a<block[i].size()||b<block[j].size();)
                  ~^~~~~~~~~~~~~~~~
elephants.cpp:52:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int a=0,b=0;a<block[i].size()||b<block[j].size();)
                                     ~^~~~~~~~~~~~~~~~
elephants.cpp:53:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(a<block[i].size()&&(b==block[i].size()||block[i][a].p<block[j][b].p))
      ~^~~~~~~~~~~~~~~~
elephants.cpp:53:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(a<block[i].size()&&(b==block[i].size()||block[i][a].p<block[j][b].p))
                          ~^~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void rebuild(std::__cxx11::list<int>::iterator)':
elephants.cpp:79:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j==block[*it].size())
      ~^~~~~~~~~~~~~~~~~~~

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