oj.uz

Submission #59092

# Submission time Handle Problem Language Result Execution time Memory
59092 2018-07-20T13:48:18 Z fallingstar Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 11920 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;
	inline bool operator < (const TElephant &b) const 
	{
		return x < b.x || (x == b.x && id < b.id);			// if x equals, compare by id
	}
}; 

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

const int BLOCK_SIZE = 600;

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;
	}
}

pair<int, int> arr[N];

void Rebuild()
{
	int m = 0;
	for (const auto &seg: a)
		for (const auto &e: seg)
			arr[m++] = {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 = 800;
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];
	TElephant old_ele {idx, x, 0, 0};
	TElephant new_ele {idx, y, 0, 0};
	
	// erase idx from old position
	for (auto i = a.begin(); i != a.end(); ++i)
		if (!(i->back() < old_ele))					// i->back >= old_ele
		{
			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, new_ele)); 
	else if (a.back().back() < new_ele)
	{
		a.back().push_back(new_ele);
		Calc(a.back());
	}	
	else 
		for (auto i = a.begin(); i != a.end(); ++i)
			if (new_ele < i->back())
			{
				for (auto it = i->begin(); it != i->end(); ++it)
					if (new_ele < *it)
					{
						i->insert(it, new_ele);
						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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 3 ms 540 KB Output is correct
6 Correct 2 ms 616 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 3 ms 540 KB Output is correct
6 Correct 2 ms 616 KB Output is correct
7 Correct 597 ms 2008 KB Output is correct
8 Correct 529 ms 2408 KB Output is correct
9 Correct 431 ms 4328 KB Output is correct
10 Correct 681 ms 4472 KB Output is correct
11 Correct 1849 ms 4472 KB Output is correct
12 Correct 1485 ms 4472 KB Output is correct
13 Correct 1247 ms 4472 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 3 ms 540 KB Output is correct
6 Correct 2 ms 616 KB Output is correct
7 Correct 597 ms 2008 KB Output is correct
8 Correct 529 ms 2408 KB Output is correct
9 Correct 431 ms 4328 KB Output is correct
10 Correct 681 ms 4472 KB Output is correct
11 Correct 1849 ms 4472 KB Output is correct
12 Correct 1485 ms 4472 KB Output is correct
13 Correct 1247 ms 4472 KB Output is correct
14 Correct 1346 ms 4472 KB Output is correct
15 Correct 572 ms 4472 KB Output is correct
16 Correct 2031 ms 4728 KB Output is correct
17 Correct 2432 ms 6012 KB Output is correct
18 Correct 2784 ms 6012 KB Output is correct
19 Correct 1030 ms 6012 KB Output is correct
20 Correct 2991 ms 6012 KB Output is correct
21 Correct 2749 ms 6012 KB Output is correct
22 Correct 2363 ms 6012 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 3 ms 540 KB Output is correct
6 Correct 2 ms 616 KB Output is correct
7 Correct 597 ms 2008 KB Output is correct
8 Correct 529 ms 2408 KB Output is correct
9 Correct 431 ms 4328 KB Output is correct
10 Correct 681 ms 4472 KB Output is correct
11 Correct 1849 ms 4472 KB Output is correct
12 Correct 1485 ms 4472 KB Output is correct
13 Correct 1247 ms 4472 KB Output is correct
14 Correct 1346 ms 4472 KB Output is correct
15 Correct 572 ms 4472 KB Output is correct
16 Correct 2031 ms 4728 KB Output is correct
17 Correct 2432 ms 6012 KB Output is correct
18 Correct 2784 ms 6012 KB Output is correct
19 Correct 1030 ms 6012 KB Output is correct
20 Correct 2991 ms 6012 KB Output is correct
21 Correct 2749 ms 6012 KB Output is correct
22 Correct 2363 ms 6012 KB Output is correct
23 Correct 4289 ms 11920 KB Output is correct
24 Correct 4733 ms 11920 KB Output is correct
25 Correct 2980 ms 11920 KB Output is correct
26 Correct 3423 ms 11920 KB Output is correct
27 Correct 3810 ms 11920 KB Output is correct
28 Correct 2152 ms 11920 KB Output is correct
29 Correct 1861 ms 11920 KB Output is correct
30 Correct 2214 ms 11920 KB Output is correct
31 Correct 1857 ms 11920 KB Output is correct
32 Execution timed out 9069 ms 11920 KB Time limit exceeded
33 Halted 0 ms 0 KB -