oj.uz

Submission #59110

# Submission time Handle Problem Language Result Execution time Memory
59110 2018-07-20T14:45:37 Z fallingstar Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5318 ms 11336 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 = 600;

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 = 400;
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 576 KB Output is correct
3 Correct 2 ms 576 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 576 KB Output is correct
3 Correct 2 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 376 KB Output is correct
2 Correct 2 ms 576 KB Output is correct
3 Correct 2 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 276 ms 1660 KB Output is correct
8 Correct 378 ms 1896 KB Output is correct
9 Correct 430 ms 4184 KB Output is correct
10 Correct 329 ms 4184 KB Output is correct
11 Correct 329 ms 4184 KB Output is correct
12 Correct 864 ms 4884 KB Output is correct
13 Correct 337 ms 4884 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 576 KB Output is correct
3 Correct 2 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 276 ms 1660 KB Output is correct
8 Correct 378 ms 1896 KB Output is correct
9 Correct 430 ms 4184 KB Output is correct
10 Correct 329 ms 4184 KB Output is correct
11 Correct 329 ms 4184 KB Output is correct
12 Correct 864 ms 4884 KB Output is correct
13 Correct 337 ms 4884 KB Output is correct
14 Correct 325 ms 4884 KB Output is correct
15 Correct 357 ms 4884 KB Output is correct
16 Correct 1264 ms 5264 KB Output is correct
17 Correct 1331 ms 6276 KB Output is correct
18 Correct 1451 ms 6404 KB Output is correct
19 Correct 745 ms 6404 KB Output is correct
20 Correct 1401 ms 6404 KB Output is correct
21 Correct 1536 ms 6404 KB Output is correct
22 Correct 637 ms 6404 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 576 KB Output is correct
3 Correct 2 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 276 ms 1660 KB Output is correct
8 Correct 378 ms 1896 KB Output is correct
9 Correct 430 ms 4184 KB Output is correct
10 Correct 329 ms 4184 KB Output is correct
11 Correct 329 ms 4184 KB Output is correct
12 Correct 864 ms 4884 KB Output is correct
13 Correct 337 ms 4884 KB Output is correct
14 Correct 325 ms 4884 KB Output is correct
15 Correct 357 ms 4884 KB Output is correct
16 Correct 1264 ms 5264 KB Output is correct
17 Correct 1331 ms 6276 KB Output is correct
18 Correct 1451 ms 6404 KB Output is correct
19 Correct 745 ms 6404 KB Output is correct
20 Correct 1401 ms 6404 KB Output is correct
21 Correct 1536 ms 6404 KB Output is correct
22 Correct 637 ms 6404 KB Output is correct
23 Correct 4570 ms 10456 KB Output is correct
24 Correct 4330 ms 10968 KB Output is correct
25 Correct 3177 ms 10968 KB Output is correct
26 Correct 3604 ms 10968 KB Output is correct
27 Correct 3624 ms 10968 KB Output is correct
28 Correct 751 ms 10968 KB Output is correct
29 Correct 742 ms 10968 KB Output is correct
30 Correct 749 ms 10968 KB Output is correct
31 Correct 689 ms 10968 KB Output is correct
32 Correct 2981 ms 10968 KB Output is correct
33 Correct 2154 ms 10968 KB Output is correct
34 Correct 3066 ms 10968 KB Output is correct
35 Correct 1943 ms 10968 KB Output is correct
36 Correct 1760 ms 10968 KB Output is correct
37 Correct 3982 ms 10968 KB Output is correct
38 Correct 2993 ms 10968 KB Output is correct
39 Correct 2870 ms 10968 KB Output is correct
40 Correct 3212 ms 10968 KB Output is correct
41 Correct 4747 ms 11336 KB Output is correct
42 Correct 5318 ms 11336 KB Output is correct