oj.uz

Submission #59096

# Submission time Handle Problem Language Result Execution time Memory
59096 2018-07-20T14:08:06 Z fallingstar Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 12096 KB 
#include "elephants.h"
#include <cassert>
#include <algorithm>
#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
	{
		auto i = lower_bound(a.begin(), a.end(), new_ele, [](const list<TElephant> &p, TElephant q) {
			return p.back() < q;
		});
		if (i != a.end())
		{
			for (auto it = i->begin(); it != i->end(); ++it)
				if (new_ele < *it)
				{
					i->insert(it, new_ele);
					break;
				}
		}
		else
		{
			--i;
			i->push_back(new_ele);
		}
		Calc(*i);
	}
	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 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 408 KB Output is correct
6 Correct 2 ms 596 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 408 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 532 ms 2008 KB Output is correct
8 Correct 471 ms 2244 KB Output is correct
9 Correct 446 ms 4260 KB Output is correct
10 Correct 703 ms 4308 KB Output is correct
11 Correct 1775 ms 4412 KB Output is correct
12 Correct 1257 ms 4412 KB Output is correct
13 Correct 1180 ms 4412 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 408 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 532 ms 2008 KB Output is correct
8 Correct 471 ms 2244 KB Output is correct
9 Correct 446 ms 4260 KB Output is correct
10 Correct 703 ms 4308 KB Output is correct
11 Correct 1775 ms 4412 KB Output is correct
12 Correct 1257 ms 4412 KB Output is correct
13 Correct 1180 ms 4412 KB Output is correct
14 Correct 1210 ms 4412 KB Output is correct
15 Correct 464 ms 4412 KB Output is correct
16 Correct 2308 ms 4680 KB Output is correct
17 Correct 2565 ms 5792 KB Output is correct
18 Correct 2337 ms 6024 KB Output is correct
19 Correct 1066 ms 6024 KB Output is correct
20 Correct 2903 ms 6024 KB Output is correct
21 Correct 2360 ms 6024 KB Output is correct
22 Correct 2281 ms 6024 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 408 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 532 ms 2008 KB Output is correct
8 Correct 471 ms 2244 KB Output is correct
9 Correct 446 ms 4260 KB Output is correct
10 Correct 703 ms 4308 KB Output is correct
11 Correct 1775 ms 4412 KB Output is correct
12 Correct 1257 ms 4412 KB Output is correct
13 Correct 1180 ms 4412 KB Output is correct
14 Correct 1210 ms 4412 KB Output is correct
15 Correct 464 ms 4412 KB Output is correct
16 Correct 2308 ms 4680 KB Output is correct
17 Correct 2565 ms 5792 KB Output is correct
18 Correct 2337 ms 6024 KB Output is correct
19 Correct 1066 ms 6024 KB Output is correct
20 Correct 2903 ms 6024 KB Output is correct
21 Correct 2360 ms 6024 KB Output is correct
22 Correct 2281 ms 6024 KB Output is correct
23 Correct 4138 ms 11804 KB Output is correct
24 Correct 4204 ms 11804 KB Output is correct
25 Correct 3037 ms 11804 KB Output is correct
26 Correct 3288 ms 12096 KB Output is correct
27 Correct 3740 ms 12096 KB Output is correct
28 Correct 1944 ms 12096 KB Output is correct
29 Correct 1789 ms 12096 KB Output is correct
30 Correct 1865 ms 12096 KB Output is correct
31 Correct 1773 ms 12096 KB Output is correct
32 Execution timed out 9071 ms 12096 KB Time limit exceeded
33 Halted 0 ms 0 KB -