oj.uz

Submission #59098

# Submission time Handle Problem Language Result Execution time Memory
59098 2018-07-20T14:18:03 Z fallingstar Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 11936 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 = 400;

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
	{
		auto i = lower_bound(a.begin(), a.end(), old_ele, [](const list<TElephant> &p, TElephant q) {
			return p.back() < q;
		});
		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));
		}
	}
	
	// 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 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 576 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 576 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 3 ms 576 KB Output is correct
6 Correct 2 ms 576 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 576 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 3 ms 576 KB Output is correct
6 Correct 2 ms 576 KB Output is correct
7 Correct 349 ms 1988 KB Output is correct
8 Correct 376 ms 2524 KB Output is correct
9 Correct 439 ms 4336 KB Output is correct
10 Correct 1090 ms 4464 KB Output is correct
11 Correct 1417 ms 4464 KB Output is correct
12 Correct 1380 ms 4464 KB Output is correct
13 Correct 1873 ms 4580 KB Output is correct

Subtask #4
47.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 576 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 3 ms 576 KB Output is correct
6 Correct 2 ms 576 KB Output is correct
7 Correct 349 ms 1988 KB Output is correct
8 Correct 376 ms 2524 KB Output is correct
9 Correct 439 ms 4336 KB Output is correct
10 Correct 1090 ms 4464 KB Output is correct
11 Correct 1417 ms 4464 KB Output is correct
12 Correct 1380 ms 4464 KB Output is correct
13 Correct 1873 ms 4580 KB Output is correct
14 Correct 1046 ms 4580 KB Output is correct
15 Correct 388 ms 4580 KB Output is correct
16 Correct 1805 ms 4592 KB Output is correct
17 Correct 2384 ms 5872 KB Output is correct
18 Correct 2700 ms 5872 KB Output is correct
19 Correct 1081 ms 5872 KB Output is correct
20 Correct 2455 ms 5872 KB Output is correct
21 Correct 2025 ms 5872 KB Output is correct
22 Correct 3408 ms 5876 KB Output is correct

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 576 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 3 ms 576 KB Output is correct
6 Correct 2 ms 576 KB Output is correct
7 Correct 349 ms 1988 KB Output is correct
8 Correct 376 ms 2524 KB Output is correct
9 Correct 439 ms 4336 KB Output is correct
10 Correct 1090 ms 4464 KB Output is correct
11 Correct 1417 ms 4464 KB Output is correct
12 Correct 1380 ms 4464 KB Output is correct
13 Correct 1873 ms 4580 KB Output is correct
14 Correct 1046 ms 4580 KB Output is correct
15 Correct 388 ms 4580 KB Output is correct
16 Correct 1805 ms 4592 KB Output is correct
17 Correct 2384 ms 5872 KB Output is correct
18 Correct 2700 ms 5872 KB Output is correct
19 Correct 1081 ms 5872 KB Output is correct
20 Correct 2455 ms 5872 KB Output is correct
21 Correct 2025 ms 5872 KB Output is correct
22 Correct 3408 ms 5876 KB Output is correct
23 Correct 4149 ms 11764 KB Output is correct
24 Correct 4495 ms 11764 KB Output is correct
25 Correct 3452 ms 11936 KB Output is correct
26 Correct 3280 ms 11936 KB Output is correct
27 Correct 3352 ms 11936 KB Output is correct
28 Correct 1557 ms 11936 KB Output is correct
29 Correct 1586 ms 11936 KB Output is correct
30 Correct 1809 ms 11936 KB Output is correct
31 Correct 1533 ms 11936 KB Output is correct
32 Execution timed out 9048 ms 11936 KB Time limit exceeded
33 Halted 0 ms 0 KB -