Submission #402749

#	Time	Username	Problem	Language	Result	Execution time	Memory
402749		Jasiekstrz	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	267 ms	6656 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int NN=15e4;
const int S=400; // how many in one block
//const int S=1;
int l;
struct Block
{
	int d;
	int t[2*S+10];
	pair<int,int> dp[2*S+10];
	Block()
	{
		d=0;
	}
	void clear()
	{
		d=0;
		return;
	}
	void recount()
	{
		dp[d]={0,0};
		for(int i=d-1,j=d;i>=0;i--)
		{
			while(t[i]+l<t[j-1])
				j--;
			dp[i].fi=dp[j].fi+1;
			if(j==d)
				dp[i].se=t[i]+l;
			else
				dp[i].se=dp[j].se;
		}
		return;
	}
	void add(int x)
	{
		int p;
		for(p=0;p<d && t[p]<x;p++);
		for(int i=d-1;i>=p;i--)
			t[i+1]=t[i];
		t[p]=x;
		d++;
		recount();
		return;
	}
	void remove(int x)
	{
		int p;
		for(p=0;p<d && t[p]<x;p++);
		for(int i=p;i<d-1;i++)
			t[i]=t[i+1];
		d--;
		recount();
		return;
	}
	pair<int,int> ans_pos(int x)
	{
		if(d==0)
			return {0,x};
		int bg=0,en=d-1;
		while(bg<en)
		{
			int mid=(bg+en)/2;
			if(t[mid]>x)
				en=mid;
			else
				bg=mid+1;
		}
		if(t[bg]<=x)
			return {0,x};
		return dp[bg];
	}
};
int n,qq=0;
Block b[NN/S+10];
int curr_pos[NN+10];
void recount_all()
{
	for(int i=0;i<=n/S;i++)
		b[i].clear();
	vector<int> tmp(n);
	for(int i=0;i<n;i++)
		tmp[i]=curr_pos[i];
	sort(tmp.begin(),tmp.end());
	for(int i=0;i<n;i++)
	{
		b[i/S].t[i%S]=tmp[i];
		b[i/S].d++;
	}
	for(int i=0;i<=n/S;i++)
		b[i].recount();
	return;
}
Block& find_block(int x)
{
	int i;
	for(i=0;i<=n/S && (b[i].d==0 || b[i].t[0]<x);i++);
	if(i==0 || b[i].t[0]==x)
		return b[i];
	return b[i-1];
}
int get_ans()
{
	int ans=0,x=-1;
	for(int i=0;i<=n/S;i++)
	{
		auto tmp=b[i].ans_pos(x);
		ans+=tmp.fi;
		x=tmp.se;
		//cerr<<"xd "<<i<<" "<<ans<<" "<<x<<"\n";
		//for(int j=0;j<b[i].d;j++)
		//	cerr<<b[i].t[j]<<" ";
		//cerr<<"\n";
	}
	return ans;
}
void init(int N,int L,int X[])
{
	n=N;
	l=L;
	for(int i=0;i<n;i++)
		curr_pos[i]=X[i];
	recount_all();
	return;
}
int update(int i,int y)
{
	if(qq>=S-10)
	{
		recount_all();
		qq=0;
	}
	qq++;
	find_block(curr_pos[i]).remove(curr_pos[i]);
	find_block(y).add(y);
	curr_pos[i]=y;
	return get_ans();
}

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