답안 #59102 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59102	2018-07-20T14:35:37 Z	fallingstar	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	5674 ms	10460 KB

elephants

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #59102

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 16.0 / 16.0

Subtask #3 24.0 / 24.0

Subtask #4 47.0 / 47.0

Subtask #5 3.0 / 3.0

Subtask #1
10.0 / 10.0

Subtask #2
16.0 / 16.0

Subtask #3
24.0 / 24.0

Subtask #4
47.0 / 47.0

Subtask #5
3.0 / 3.0