oj.uz

Submission #59091

# Submission time Handle Problem Language Result Execution time Memory
59091 2018-07-20T13:45:11 Z fallingstar Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 48136 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 = 1200;
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 488 KB Output is correct
3 Correct 3 ms 552 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 488 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Correct 2 ms 552 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 488 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 595 ms 1956 KB Output is correct
8 Correct 698 ms 2224 KB Output is correct
9 Correct 436 ms 4276 KB Output is correct
10 Correct 697 ms 4396 KB Output is correct
11 Correct 1742 ms 4400 KB Output is correct
12 Correct 1468 ms 4400 KB Output is correct
13 Correct 1197 ms 4400 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 488 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 595 ms 1956 KB Output is correct
8 Correct 698 ms 2224 KB Output is correct
9 Correct 436 ms 4276 KB Output is correct
10 Correct 697 ms 4396 KB Output is correct
11 Correct 1742 ms 4400 KB Output is correct
12 Correct 1468 ms 4400 KB Output is correct
13 Correct 1197 ms 4400 KB Output is correct
14 Correct 1558 ms 4400 KB Output is correct
15 Correct 574 ms 4400 KB Output is correct
16 Correct 2313 ms 4684 KB Output is correct
17 Correct 2371 ms 5956 KB Output is correct
18 Correct 3332 ms 5956 KB Output is correct
19 Correct 985 ms 5956 KB Output is correct
20 Correct 2279 ms 5956 KB Output is correct
21 Correct 2391 ms 5956 KB Output is correct
22 Correct 2340 ms 5956 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 488 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 595 ms 1956 KB Output is correct
8 Correct 698 ms 2224 KB Output is correct
9 Correct 436 ms 4276 KB Output is correct
10 Correct 697 ms 4396 KB Output is correct
11 Correct 1742 ms 4400 KB Output is correct
12 Correct 1468 ms 4400 KB Output is correct
13 Correct 1197 ms 4400 KB Output is correct
14 Correct 1558 ms 4400 KB Output is correct
15 Correct 574 ms 4400 KB Output is correct
16 Correct 2313 ms 4684 KB Output is correct
17 Correct 2371 ms 5956 KB Output is correct
18 Correct 3332 ms 5956 KB Output is correct
19 Correct 985 ms 5956 KB Output is correct
20 Correct 2279 ms 5956 KB Output is correct
21 Correct 2391 ms 5956 KB Output is correct
22 Correct 2340 ms 5956 KB Output is correct
23 Correct 4515 ms 11804 KB Output is correct
24 Correct 5028 ms 17020 KB Output is correct
25 Correct 3079 ms 21988 KB Output is correct
26 Correct 3522 ms 27076 KB Output is correct
27 Correct 3254 ms 31924 KB Output is correct
28 Correct 2196 ms 31924 KB Output is correct
29 Correct 2060 ms 31924 KB Output is correct
30 Correct 2052 ms 31924 KB Output is correct
31 Correct 1939 ms 34592 KB Output is correct
32 Execution timed out 9055 ms 48136 KB Time limit exceeded
33 Halted 0 ms 0 KB -