답안 #59114 :: oj.uz

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

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

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

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

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

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

답안 #59114

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