답안 #59099 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59099	2018-07-20T14:29:35 Z	fallingstar	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	8551 ms	54456 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
		{
			for (auto it = i->begin(); it != i->end(); ++it)
				if (it->x >= curX)
				{
					ans += it->f + 1;					// jump inner-segment, then to new segment
					curX = it->xDest + L + 1;
					break;
				}
		}
	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	2 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	2 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct
6	Correct	2 ms	564 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	2 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct
6	Correct	2 ms	564 KB	Output is correct
7	Correct	253 ms	1668 KB	Output is correct
8	Correct	294 ms	1964 KB	Output is correct
9	Correct	294 ms	3876 KB	Output is correct
10	Correct	444 ms	3876 KB	Output is correct
11	Correct	538 ms	3876 KB	Output is correct
12	Correct	446 ms	4924 KB	Output is correct
13	Correct	742 ms	4924 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	2 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct
6	Correct	2 ms	564 KB	Output is correct
7	Correct	253 ms	1668 KB	Output is correct
8	Correct	294 ms	1964 KB	Output is correct
9	Correct	294 ms	3876 KB	Output is correct
10	Correct	444 ms	3876 KB	Output is correct
11	Correct	538 ms	3876 KB	Output is correct
12	Correct	446 ms	4924 KB	Output is correct
13	Correct	742 ms	4924 KB	Output is correct
14	Correct	293 ms	4924 KB	Output is correct
15	Correct	323 ms	4924 KB	Output is correct
16	Correct	737 ms	5304 KB	Output is correct
17	Correct	897 ms	6256 KB	Output is correct
18	Correct	1053 ms	6276 KB	Output is correct
19	Correct	538 ms	6276 KB	Output is correct
20	Correct	863 ms	6276 KB	Output is correct
21	Correct	885 ms	6276 KB	Output is correct
22	Correct	1404 ms	6276 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	2 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct
6	Correct	2 ms	564 KB	Output is correct
7	Correct	253 ms	1668 KB	Output is correct
8	Correct	294 ms	1964 KB	Output is correct
9	Correct	294 ms	3876 KB	Output is correct
10	Correct	444 ms	3876 KB	Output is correct
11	Correct	538 ms	3876 KB	Output is correct
12	Correct	446 ms	4924 KB	Output is correct
13	Correct	742 ms	4924 KB	Output is correct
14	Correct	293 ms	4924 KB	Output is correct
15	Correct	323 ms	4924 KB	Output is correct
16	Correct	737 ms	5304 KB	Output is correct
17	Correct	897 ms	6256 KB	Output is correct
18	Correct	1053 ms	6276 KB	Output is correct
19	Correct	538 ms	6276 KB	Output is correct
20	Correct	863 ms	6276 KB	Output is correct
21	Correct	885 ms	6276 KB	Output is correct
22	Correct	1404 ms	6276 KB	Output is correct
23	Correct	2713 ms	9916 KB	Output is correct
24	Correct	2735 ms	10136 KB	Output is correct
25	Correct	1631 ms	10136 KB	Output is correct
26	Correct	1906 ms	10136 KB	Output is correct
27	Correct	1671 ms	10136 KB	Output is correct
28	Correct	805 ms	10136 KB	Output is correct
29	Correct	715 ms	10136 KB	Output is correct
30	Correct	853 ms	10136 KB	Output is correct
31	Correct	781 ms	10136 KB	Output is correct
32	Correct	3817 ms	10136 KB	Output is correct
33	Correct	1507 ms	11724 KB	Output is correct
34	Correct	3928 ms	16488 KB	Output is correct
35	Correct	1268 ms	21240 KB	Output is correct
36	Correct	1474 ms	27736 KB	Output is correct
37	Correct	2687 ms	32996 KB	Output is correct
38	Correct	6736 ms	34300 KB	Output is correct
39	Correct	2126 ms	39040 KB	Output is correct
40	Correct	8551 ms	42592 KB	Output is correct
41	Correct	3039 ms	49920 KB	Output is correct
42	Correct	3412 ms	54456 KB	Output is correct

답안 #59099

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