답안 #59116 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59116	2018-07-20T14:59:51 Z	fallingstar	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	5635 ms	10852 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	3 ms	248 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct
4	Correct	3 ms	484 KB	Output is correct
5	Correct	2 ms	484 KB	Output is correct
6	Correct	3 ms	484 KB	Output is correct
7	Correct	325 ms	1652 KB	Output is correct
8	Correct	345 ms	1824 KB	Output is correct
9	Correct	480 ms	3960 KB	Output is correct
10	Correct	336 ms	3960 KB	Output is correct
11	Correct	380 ms	3960 KB	Output is correct
12	Correct	875 ms	4924 KB	Output is correct
13	Correct	390 ms	4924 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct
4	Correct	3 ms	484 KB	Output is correct
5	Correct	2 ms	484 KB	Output is correct
6	Correct	3 ms	484 KB	Output is correct
7	Correct	325 ms	1652 KB	Output is correct
8	Correct	345 ms	1824 KB	Output is correct
9	Correct	480 ms	3960 KB	Output is correct
10	Correct	336 ms	3960 KB	Output is correct
11	Correct	380 ms	3960 KB	Output is correct
12	Correct	875 ms	4924 KB	Output is correct
13	Correct	390 ms	4924 KB	Output is correct
14	Correct	333 ms	4924 KB	Output is correct
15	Correct	379 ms	4924 KB	Output is correct
16	Correct	1216 ms	5144 KB	Output is correct
17	Correct	1266 ms	6216 KB	Output is correct
18	Correct	1549 ms	6264 KB	Output is correct
19	Correct	1137 ms	6264 KB	Output is correct
20	Correct	1626 ms	6300 KB	Output is correct
21	Correct	1415 ms	6300 KB	Output is correct
22	Correct	946 ms	6300 KB	Output is correct

Subtask #5
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct
4	Correct	3 ms	484 KB	Output is correct
5	Correct	2 ms	484 KB	Output is correct
6	Correct	3 ms	484 KB	Output is correct
7	Correct	325 ms	1652 KB	Output is correct
8	Correct	345 ms	1824 KB	Output is correct
9	Correct	480 ms	3960 KB	Output is correct
10	Correct	336 ms	3960 KB	Output is correct
11	Correct	380 ms	3960 KB	Output is correct
12	Correct	875 ms	4924 KB	Output is correct
13	Correct	390 ms	4924 KB	Output is correct
14	Correct	333 ms	4924 KB	Output is correct
15	Correct	379 ms	4924 KB	Output is correct
16	Correct	1216 ms	5144 KB	Output is correct
17	Correct	1266 ms	6216 KB	Output is correct
18	Correct	1549 ms	6264 KB	Output is correct
19	Correct	1137 ms	6264 KB	Output is correct
20	Correct	1626 ms	6300 KB	Output is correct
21	Correct	1415 ms	6300 KB	Output is correct
22	Correct	946 ms	6300 KB	Output is correct
23	Correct	4495 ms	10012 KB	Output is correct
24	Correct	4858 ms	10388 KB	Output is correct
25	Correct	3093 ms	10388 KB	Output is correct
26	Correct	3045 ms	10388 KB	Output is correct
27	Correct	3407 ms	10388 KB	Output is correct
28	Correct	671 ms	10388 KB	Output is correct
29	Correct	642 ms	10388 KB	Output is correct
30	Correct	713 ms	10388 KB	Output is correct
31	Correct	609 ms	10388 KB	Output is correct
32	Correct	3031 ms	10388 KB	Output is correct
33	Correct	1823 ms	10388 KB	Output is correct
34	Correct	2370 ms	10388 KB	Output is correct
35	Correct	1965 ms	10388 KB	Output is correct
36	Correct	2272 ms	10388 KB	Output is correct
37	Correct	4325 ms	10532 KB	Output is correct
38	Correct	2614 ms	10532 KB	Output is correct
39	Correct	3128 ms	10532 KB	Output is correct
40	Correct	2569 ms	10532 KB	Output is correct
41	Correct	5581 ms	10676 KB	Output is correct
42	Correct	5635 ms	10852 KB	Output is correct

답안 #59116

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