oj.uz

Submission #59102

# Submission time Handle Problem Language Result Execution time Memory
59102 2018-07-20T14:35:37 Z fallingstar Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5674 ms 10460 KB 
#include "elephants.h"
#include <cassert>
#include <algorithm>
#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<vector<TElephant> > a;
int pos[N];

const int BLOCK_SIZE = 400;

void Calc(vector<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();
	vector<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;
	vector<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
		{
			auto it = lower_bound(i->begin(), i->end(), curX, [](TElephant p, int q) { 
				return p.x < q;
			});
			ans += it->f + 1;					// jump inner-segment, then to new segment
			curX = it->xDest + L + 1;	
		}
	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 vector<TElephant> &p, TElephant q) {
			return p.back() < q;
		});
		vector<TElephant> leftSeg;
		for (auto it = i->begin(); it != i->end(); ++it)
			if (it->id == idx)
			{
				// cut segment into 2 parts
				leftSeg = vector<TElephant>(i->begin(), it);
				i->erase(i->begin(), next(it));
				break;
			}
		if (i->empty()) i = a.erase(i);
		if (!leftSeg.empty()) 
		{
			Calc(leftSeg);
			a.insert(i, move(leftSeg));
		}
	}
	
	// insert idx to new position
	if (a.empty()) 
		a.push_back(vector<TElephant>(1, new_ele)); 
	else
	{
		auto i = lower_bound(a.begin(), a.end(), new_ele, [](const vector<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 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 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 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 2 ms 516 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 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 2 ms 516 KB Output is correct
7 Correct 260 ms 1680 KB Output is correct
8 Correct 274 ms 1932 KB Output is correct
9 Correct 572 ms 3988 KB Output is correct
10 Correct 344 ms 3988 KB Output is correct
11 Correct 379 ms 3988 KB Output is correct
12 Correct 978 ms 5032 KB Output is correct
13 Correct 395 ms 5032 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 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 2 ms 516 KB Output is correct
7 Correct 260 ms 1680 KB Output is correct
8 Correct 274 ms 1932 KB Output is correct
9 Correct 572 ms 3988 KB Output is correct
10 Correct 344 ms 3988 KB Output is correct
11 Correct 379 ms 3988 KB Output is correct
12 Correct 978 ms 5032 KB Output is correct
13 Correct 395 ms 5032 KB Output is correct
14 Correct 374 ms 5032 KB Output is correct
15 Correct 341 ms 5032 KB Output is correct
16 Correct 1514 ms 5188 KB Output is correct
17 Correct 1529 ms 6172 KB Output is correct
18 Correct 1603 ms 6440 KB Output is correct
19 Correct 850 ms 6440 KB Output is correct
20 Correct 1623 ms 6440 KB Output is correct
21 Correct 1589 ms 6440 KB Output is correct
22 Correct 678 ms 6440 KB Output is correct

Subtask #5
3.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 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 2 ms 516 KB Output is correct
7 Correct 260 ms 1680 KB Output is correct
8 Correct 274 ms 1932 KB Output is correct
9 Correct 572 ms 3988 KB Output is correct
10 Correct 344 ms 3988 KB Output is correct
11 Correct 379 ms 3988 KB Output is correct
12 Correct 978 ms 5032 KB Output is correct
13 Correct 395 ms 5032 KB Output is correct
14 Correct 374 ms 5032 KB Output is correct
15 Correct 341 ms 5032 KB Output is correct
16 Correct 1514 ms 5188 KB Output is correct
17 Correct 1529 ms 6172 KB Output is correct
18 Correct 1603 ms 6440 KB Output is correct
19 Correct 850 ms 6440 KB Output is correct
20 Correct 1623 ms 6440 KB Output is correct
21 Correct 1589 ms 6440 KB Output is correct
22 Correct 678 ms 6440 KB Output is correct
23 Correct 4840 ms 9916 KB Output is correct
24 Correct 4865 ms 10100 KB Output is correct
25 Correct 3699 ms 10100 KB Output is correct
26 Correct 3320 ms 10100 KB Output is correct
27 Correct 2861 ms 10100 KB Output is correct
28 Correct 737 ms 10100 KB Output is correct
29 Correct 682 ms 10100 KB Output is correct
30 Correct 724 ms 10100 KB Output is correct
31 Correct 649 ms 10100 KB Output is correct
32 Correct 2274 ms 10100 KB Output is correct
33 Correct 2123 ms 10100 KB Output is correct
34 Correct 2463 ms 10100 KB Output is correct
35 Correct 1633 ms 10100 KB Output is correct
36 Correct 1671 ms 10100 KB Output is correct
37 Correct 4777 ms 10196 KB Output is correct
38 Correct 3028 ms 10196 KB Output is correct
39 Correct 2789 ms 10196 KB Output is correct
40 Correct 3110 ms 10196 KB Output is correct
41 Correct 5674 ms 10460 KB Output is correct
42 Correct 5360 ms 10460 KB Output is correct