답안 #59097 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59097	2018-07-20T14:14:26 Z	fallingstar	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	97 / 100	9000 ms	11792 KB

elephants

#include "elephants.h"
#include <cassert>
#include <algorithm>
#include <list>
#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<list<TElephant> > a;
int pos[N];

const int BLOCK_SIZE = 600;

void Calc(list<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();
	list<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;
	list<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 list<TElephant> &p, TElephant q) {
			return p.back() < q;
		});
		list<TElephant> leftSeg;
		for (auto it = i->begin(); it != i->end(); ++it)
			if (it->id == idx)
			{
				// cut segment into 2 parts
				leftSeg.splice(leftSeg.end(), *i, i->begin(), next(it));
				break;
			}
		if (i->empty()) i = a.erase(i);
		leftSeg.pop_back();
		if (!leftSeg.empty()) 
		{
			Calc(leftSeg);
			a.insert(i, move(leftSeg));
		}
	}
	
	// insert idx to new position
	if (a.empty()) 
		a.push_back(list<TElephant>(1, new_ele)); 
	else
	{
		auto i = lower_bound(a.begin(), a.end(), new_ele, [](const list<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	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	3 ms	560 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	3 ms	560 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct
5	Correct	2 ms	640 KB	Output is correct
6	Correct	3 ms	640 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	3 ms	560 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct
5	Correct	2 ms	640 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	469 ms	2084 KB	Output is correct
8	Correct	524 ms	2232 KB	Output is correct
9	Correct	438 ms	4340 KB	Output is correct
10	Correct	752 ms	4428 KB	Output is correct
11	Correct	1880 ms	4428 KB	Output is correct
12	Correct	1432 ms	4428 KB	Output is correct
13	Correct	1259 ms	4476 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	3 ms	560 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct
5	Correct	2 ms	640 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	469 ms	2084 KB	Output is correct
8	Correct	524 ms	2232 KB	Output is correct
9	Correct	438 ms	4340 KB	Output is correct
10	Correct	752 ms	4428 KB	Output is correct
11	Correct	1880 ms	4428 KB	Output is correct
12	Correct	1432 ms	4428 KB	Output is correct
13	Correct	1259 ms	4476 KB	Output is correct
14	Correct	1159 ms	4476 KB	Output is correct
15	Correct	404 ms	4476 KB	Output is correct
16	Correct	1836 ms	4648 KB	Output is correct
17	Correct	2374 ms	5900 KB	Output is correct
18	Correct	2495 ms	6012 KB	Output is correct
19	Correct	1182 ms	6012 KB	Output is correct
20	Correct	2331 ms	6012 KB	Output is correct
21	Correct	2126 ms	6016 KB	Output is correct
22	Correct	2439 ms	6016 KB	Output is correct

Subtask #5
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	3 ms	560 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct
5	Correct	2 ms	640 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	469 ms	2084 KB	Output is correct
8	Correct	524 ms	2232 KB	Output is correct
9	Correct	438 ms	4340 KB	Output is correct
10	Correct	752 ms	4428 KB	Output is correct
11	Correct	1880 ms	4428 KB	Output is correct
12	Correct	1432 ms	4428 KB	Output is correct
13	Correct	1259 ms	4476 KB	Output is correct
14	Correct	1159 ms	4476 KB	Output is correct
15	Correct	404 ms	4476 KB	Output is correct
16	Correct	1836 ms	4648 KB	Output is correct
17	Correct	2374 ms	5900 KB	Output is correct
18	Correct	2495 ms	6012 KB	Output is correct
19	Correct	1182 ms	6012 KB	Output is correct
20	Correct	2331 ms	6012 KB	Output is correct
21	Correct	2126 ms	6016 KB	Output is correct
22	Correct	2439 ms	6016 KB	Output is correct
23	Correct	4067 ms	11772 KB	Output is correct
24	Correct	4460 ms	11772 KB	Output is correct
25	Correct	3221 ms	11772 KB	Output is correct
26	Correct	3354 ms	11772 KB	Output is correct
27	Correct	3518 ms	11792 KB	Output is correct
28	Correct	1682 ms	11792 KB	Output is correct
29	Correct	1645 ms	11792 KB	Output is correct
30	Correct	1739 ms	11792 KB	Output is correct
31	Correct	1391 ms	11792 KB	Output is correct
32	Execution timed out	9008 ms	11792 KB	Time limit exceeded
33	Halted	0 ms	0 KB	-

답안 #59097

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 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
0 / 3.0