답안 #59110 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59110	2018-07-20T14:45:37 Z	fallingstar	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	5318 ms	11336 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 = 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

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

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

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

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

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

답안 #59110

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