oj.uz

Submission #59083

# Submission time Handle Problem Language Result Execution time Memory
59083 2018-07-20T13:18:28 Z fallingstar Dancing Elephants (IOI11_elephants) C++14
50 / 100
 2292 ms 15224 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 676 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 676 KB Output is correct
4 Correct 3 ms 796 KB Output is correct
5 Correct 2 ms 828 KB Output is correct
6 Correct 3 ms 976 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 676 KB Output is correct
4 Correct 3 ms 796 KB Output is correct
5 Correct 2 ms 828 KB Output is correct
6 Correct 3 ms 976 KB Output is correct
7 Correct 398 ms 3536 KB Output is correct
8 Correct 473 ms 5168 KB Output is correct
9 Correct 783 ms 8956 KB Output is correct
10 Correct 1362 ms 10404 KB Output is correct
11 Correct 1685 ms 11500 KB Output is correct
12 Correct 1573 ms 13128 KB Output is correct
13 Correct 2292 ms 14176 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 676 KB Output is correct
4 Correct 3 ms 796 KB Output is correct
5 Correct 2 ms 828 KB Output is correct
6 Correct 3 ms 976 KB Output is correct
7 Correct 398 ms 3536 KB Output is correct
8 Correct 473 ms 5168 KB Output is correct
9 Correct 783 ms 8956 KB Output is correct
10 Correct 1362 ms 10404 KB Output is correct
11 Correct 1685 ms 11500 KB Output is correct
12 Correct 1573 ms 13128 KB Output is correct
13 Correct 2292 ms 14176 KB Output is correct
14 Runtime error 149 ms 15224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 676 KB Output is correct
4 Correct 3 ms 796 KB Output is correct
5 Correct 2 ms 828 KB Output is correct
6 Correct 3 ms 976 KB Output is correct
7 Correct 398 ms 3536 KB Output is correct
8 Correct 473 ms 5168 KB Output is correct
9 Correct 783 ms 8956 KB Output is correct
10 Correct 1362 ms 10404 KB Output is correct
11 Correct 1685 ms 11500 KB Output is correct
12 Correct 1573 ms 13128 KB Output is correct
13 Correct 2292 ms 14176 KB Output is correct
14 Runtime error 149 ms 15224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -