oj.uz

Submission #59114

# Submission time Handle Problem Language Result Execution time Memory
59114 2018-07-20T14:53:37 Z fallingstar Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5686 ms 10920 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;
		auto it = lower_bound(i->begin(), i->end(), old_ele);
		
		// cut segment into 2 parts
		leftSeg = vector<TElephant>(i->begin(), it);
		i->erase(i->begin(), next(it));
			
		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())
		{
			auto it = lower_bound(i->begin(), i->end(), new_ele);
			i->insert(it, new_ele);
		}
		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 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 3 ms 488 KB Output is correct
6 Correct 4 ms 488 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 3 ms 488 KB Output is correct
6 Correct 4 ms 488 KB Output is correct
7 Correct 327 ms 1724 KB Output is correct
8 Correct 431 ms 1976 KB Output is correct
9 Correct 489 ms 4132 KB Output is correct
10 Correct 328 ms 4132 KB Output is correct
11 Correct 317 ms 4132 KB Output is correct
12 Correct 804 ms 5032 KB Output is correct
13 Correct 369 ms 5032 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 3 ms 488 KB Output is correct
6 Correct 4 ms 488 KB Output is correct
7 Correct 327 ms 1724 KB Output is correct
8 Correct 431 ms 1976 KB Output is correct
9 Correct 489 ms 4132 KB Output is correct
10 Correct 328 ms 4132 KB Output is correct
11 Correct 317 ms 4132 KB Output is correct
12 Correct 804 ms 5032 KB Output is correct
13 Correct 369 ms 5032 KB Output is correct
14 Correct 437 ms 5032 KB Output is correct
15 Correct 348 ms 5032 KB Output is correct
16 Correct 1248 ms 5312 KB Output is correct
17 Correct 1369 ms 6348 KB Output is correct
18 Correct 1445 ms 6348 KB Output is correct
19 Correct 883 ms 6348 KB Output is correct
20 Correct 1405 ms 6400 KB Output is correct
21 Correct 1307 ms 6400 KB Output is correct
22 Correct 597 ms 6400 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 3 ms 488 KB Output is correct
6 Correct 4 ms 488 KB Output is correct
7 Correct 327 ms 1724 KB Output is correct
8 Correct 431 ms 1976 KB Output is correct
9 Correct 489 ms 4132 KB Output is correct
10 Correct 328 ms 4132 KB Output is correct
11 Correct 317 ms 4132 KB Output is correct
12 Correct 804 ms 5032 KB Output is correct
13 Correct 369 ms 5032 KB Output is correct
14 Correct 437 ms 5032 KB Output is correct
15 Correct 348 ms 5032 KB Output is correct
16 Correct 1248 ms 5312 KB Output is correct
17 Correct 1369 ms 6348 KB Output is correct
18 Correct 1445 ms 6348 KB Output is correct
19 Correct 883 ms 6348 KB Output is correct
20 Correct 1405 ms 6400 KB Output is correct
21 Correct 1307 ms 6400 KB Output is correct
22 Correct 597 ms 6400 KB Output is correct
23 Correct 4454 ms 10424 KB Output is correct
24 Correct 4458 ms 10900 KB Output is correct
25 Correct 3451 ms 10900 KB Output is correct
26 Correct 3081 ms 10900 KB Output is correct
27 Correct 3433 ms 10900 KB Output is correct
28 Correct 656 ms 10900 KB Output is correct
29 Correct 602 ms 10900 KB Output is correct
30 Correct 656 ms 10900 KB Output is correct
31 Correct 643 ms 10900 KB Output is correct
32 Correct 2853 ms 10900 KB Output is correct
33 Correct 2344 ms 10900 KB Output is correct
34 Correct 2695 ms 10900 KB Output is correct
35 Correct 2273 ms 10900 KB Output is correct
36 Correct 1989 ms 10900 KB Output is correct
37 Correct 4183 ms 10904 KB Output is correct
38 Correct 2846 ms 10904 KB Output is correct
39 Correct 2988 ms 10904 KB Output is correct
40 Correct 2760 ms 10904 KB Output is correct
41 Correct 5686 ms 10920 KB Output is correct
42 Correct 5191 ms 10920 KB Output is correct