답안 #59115 :: oj.uz

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

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, [](const 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;
		});
		// insert new elephant to its segment then recalculate the segment
		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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	2 ms	536 KB	Output is correct
5	Correct	2 ms	536 KB	Output is correct
6	Correct	2 ms	536 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	2 ms	536 KB	Output is correct
5	Correct	2 ms	536 KB	Output is correct
6	Correct	2 ms	536 KB	Output is correct
7	Correct	280 ms	1616 KB	Output is correct
8	Correct	383 ms	2044 KB	Output is correct
9	Correct	545 ms	3836 KB	Output is correct
10	Correct	327 ms	3836 KB	Output is correct
11	Correct	375 ms	3836 KB	Output is correct
12	Correct	771 ms	4876 KB	Output is correct
13	Correct	337 ms	4876 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	2 ms	536 KB	Output is correct
5	Correct	2 ms	536 KB	Output is correct
6	Correct	2 ms	536 KB	Output is correct
7	Correct	280 ms	1616 KB	Output is correct
8	Correct	383 ms	2044 KB	Output is correct
9	Correct	545 ms	3836 KB	Output is correct
10	Correct	327 ms	3836 KB	Output is correct
11	Correct	375 ms	3836 KB	Output is correct
12	Correct	771 ms	4876 KB	Output is correct
13	Correct	337 ms	4876 KB	Output is correct
14	Correct	316 ms	4876 KB	Output is correct
15	Correct	380 ms	4876 KB	Output is correct
16	Correct	1141 ms	5196 KB	Output is correct
17	Correct	1436 ms	6232 KB	Output is correct
18	Correct	1454 ms	6488 KB	Output is correct
19	Correct	863 ms	6488 KB	Output is correct
20	Correct	1569 ms	6488 KB	Output is correct
21	Correct	1593 ms	6488 KB	Output is correct
22	Correct	677 ms	6488 KB	Output is correct

Subtask #5
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	2 ms	536 KB	Output is correct
5	Correct	2 ms	536 KB	Output is correct
6	Correct	2 ms	536 KB	Output is correct
7	Correct	280 ms	1616 KB	Output is correct
8	Correct	383 ms	2044 KB	Output is correct
9	Correct	545 ms	3836 KB	Output is correct
10	Correct	327 ms	3836 KB	Output is correct
11	Correct	375 ms	3836 KB	Output is correct
12	Correct	771 ms	4876 KB	Output is correct
13	Correct	337 ms	4876 KB	Output is correct
14	Correct	316 ms	4876 KB	Output is correct
15	Correct	380 ms	4876 KB	Output is correct
16	Correct	1141 ms	5196 KB	Output is correct
17	Correct	1436 ms	6232 KB	Output is correct
18	Correct	1454 ms	6488 KB	Output is correct
19	Correct	863 ms	6488 KB	Output is correct
20	Correct	1569 ms	6488 KB	Output is correct
21	Correct	1593 ms	6488 KB	Output is correct
22	Correct	677 ms	6488 KB	Output is correct
23	Correct	3935 ms	9840 KB	Output is correct
24	Correct	3993 ms	10316 KB	Output is correct
25	Correct	2838 ms	10316 KB	Output is correct
26	Correct	2663 ms	10316 KB	Output is correct
27	Correct	3261 ms	10316 KB	Output is correct
28	Correct	666 ms	10316 KB	Output is correct
29	Correct	643 ms	10316 KB	Output is correct
30	Correct	738 ms	10316 KB	Output is correct
31	Correct	610 ms	10316 KB	Output is correct
32	Correct	3032 ms	10316 KB	Output is correct
33	Correct	1772 ms	10316 KB	Output is correct
34	Correct	2496 ms	10316 KB	Output is correct
35	Correct	1838 ms	10316 KB	Output is correct
36	Correct	2145 ms	10316 KB	Output is correct
37	Correct	3984 ms	10600 KB	Output is correct
38	Correct	2865 ms	10600 KB	Output is correct
39	Correct	3430 ms	10600 KB	Output is correct
40	Correct	2687 ms	10600 KB	Output is correct
41	Correct	5537 ms	10692 KB	Output is correct
42	Correct	5571 ms	10692 KB	Output is correct

답안 #59115

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