Submission #59083

#	Time	Username	Problem	Language	Result	Execution time	Memory
59083		fallingstar	Dancing Elephants (IOI11_elephants)	C++14	50 / 100	2292 ms	15224 KiB

elephants

#include "elephants.h"
#include <list>
#include <vector>

using namespace std;

const int N = 1.5e5;

int n, L;

struct TElephant { 
	int id, x;
	int f, xDest;
}; 

list<list<TElephant> > a;
int pos[N];

const int BLOCK_SIZE = 387;

void Calc(list<TElephant> &seg)
{
	auto itR = prev(seg.end()), itL = itR;
	itL->f = 0, itL->xDest = itL->x;
	while (itL != seg.begin())
	{
		--itL;
		while (itR != itL && itL->x + L < prev(itR)->x) itR = prev(itR);
		if (itL->x + L < itR->x)
		{
			itL->f = itR->f + 1;
			itL->xDest = itR->xDest;
		}
		else 
			itL->f = 0, itL->xDest = itL->x;
	}
}

void Rebuild()
{
	vector<pair<int, int> > arr;
	for (const auto &seg: a)
		for (const auto &e: seg)
			arr.push_back({e.id, e.x});
	
	a.clear();
	list<TElephant> cur;
	for (int i = 0; i < n; ++i)
	{
		cur.push_back({arr[i].first, arr[i].second, 0, arr[i].second});
		if (cur.size() >= BLOCK_SIZE || i == n - 1) 
		{
			Calc(cur);
			a.push_back(move(cur));
			cur.clear();
		}
	}
}

void init(int numElephants, int camWidth, int X[])
{
	n = numElephants;
	L = camWidth;
	list<TElephant> sentinel;
	for (int i = 0; i < n; ++i) 
	{
		pos[i] = X[i];
		sentinel.push_back({i, X[i], 0, 0});
	}
	a.push_back(move(sentinel));
	Rebuild();
}

const int STACK_SIZE = 387;
int countQuery = 0;

int GetAns() 
{
	int ans = 0, curX = a.begin()->begin()->x;
	for (auto i = a.begin(); i != a.end(); ++i)
		if (prev(i->end())->x >= curX)					// if segment contain current X
		{
			for (auto it = i->begin(); it != i->end(); ++it)
				if (it->x >= curX)
				{
					ans += it->f + 1;					// jump inner-segment, then to new segment
					curX = it->xDest + L + 1;
					break;
				}
		}
	return ans;
}

int update(int idx, int y)
{
	int x = pos[idx];
	
	// erase idx from old position
	for (auto i = a.begin(); i != a.end(); ++i)
		if (prev(i->end())->x >= x)
		{
			list<TElephant> leftSeg;
			for (auto it = i->begin(); it != i->end(); ++it)
				if (it->id == idx)
				{
					// cut segment into 2 parts
					leftSeg.splice(leftSeg.end(), *i, i->begin(), next(it));
					break;
				}
			if (i->empty()) i = a.erase(i);
			leftSeg.pop_back();
			if (!leftSeg.empty()) 
			{
				Calc(leftSeg);
				a.insert(i, move(leftSeg));
			}
			break;
		}
	
	// insert idx to new position
	if (a.empty()) 
		a.push_back(list<TElephant>(1, {idx, y, 0, 0})); 
	else if (y > a.back().back().x)
	{
		a.back().push_back({idx, y, 0, 0});
		Calc(a.back());
	}	
	else 
		for (auto i = a.begin(); i != a.end(); ++i)
			if (i->back().x >= y)
			{
				for (auto it = i->begin(); it != i->end(); ++it)
					if (it->x >= y)
					{
						i->insert(it, {idx, y, 0, 0});
						break;
					}
				Calc(*i);
				break;
			}
	
	pos[idx] = y;
	++countQuery;
	if (countQuery >= STACK_SIZE) Rebuild(), countQuery = 0;
	return GetAns();
}

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