답안 #62060 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62060	2018-07-27T10:58:57 Z	aome	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	100 / 100	8025 ms	119752 KB

elephants

#include "elephants.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 150005;
const int B = 500;

int n, L;
int a[N], in[N];
int jump[N], f[N];
int szVec;
vector<int> arr;
vector< pair<int, int> > vec[N];

void calc(vector< pair<int, int> > &vec) {
	int ptr = 0, sz = vec.size();
	for (int i = 0; i < sz; ++i) {
		while (ptr < sz && vec[ptr].first <= vec[i].first + L) ptr++;
		if (ptr == sz) jump[vec[i].second] = vec[i].second;
		else jump[vec[i].second] = vec[ptr].second;
	}
	for (int i = sz - 1; i >= 0; --i) {
		int j = vec[i].second;
		int k = jump[j];
		if (k == j) f[j] = 0;
		else {
			f[j] = f[k] + 1;
			if (jump[k] != -1) jump[j] = jump[k];
		}
	}
}

void init(int _n, int _L, int X[]) {
	n = _n, L = _L;
	for (int i = 0; i < n; ++i) a[i] = X[i];
	for (int i = 0; i < n; i += B) {
		int r = min(n, i + B) - 1;
		for (int j = i; j <= r; ++j) {
			vec[szVec].push_back({a[j], j});
			in[j] = szVec;
		}
		calc(vec[szVec]), arr.push_back(szVec++);
	}
}

void push(int p, int x) {
	vector< pair<int, int> > &cur = vec[arr[p]];
	vector< pair<int, int> > buf = cur; cur.clear();
	bool flag = 0;
	for (auto i : buf) {
		if (!flag && i.first > a[x]) {
			flag = 1, cur.push_back({a[x], x});
		}	
		cur.push_back(i);
	}
	if (!flag) cur.push_back({a[x], x});
	buf.clear();
	if (cur.size() == B * 2) {
		for (int i = B; i < B * 2; ++i) {
			buf.push_back(cur[i]);
			in[cur[i].second] = szVec;
		}
		cur.resize(B);
		arr.insert(arr.begin() + p + 1, szVec);
		vec[szVec++] = buf;
		calc(cur), calc(buf);
	}
	else {
		calc(cur);
	}
}

int get() {
	// for (int i = 0; i < n; ++i) cout << a[i] << ' ' << jump[i] << ' ' << f[i] << '\n';
	// for (auto i : arr) {
	// 	cout << "#\n";
	// 	for (auto j : vec[i]) cout << j.first << ' ' << j.second << '\n';
	// }
	int res = 0, cur = -1e9;
	for (auto i : arr) {
		if (vec[i].back().first <= cur) continue;
		// cout << cur << '\n';
		++res;
		auto j = lower_bound(vec[i].begin(), vec[i].end(), make_pair(cur + 1, 0));
		res += f[j -> second];
		cur = a[jump[j -> second]] + L;
	}
	return res;
}

int update(int x, int y) {
	if (n == 1) return 1;
	for (int i = 0; i < arr.size(); ++i) {
		int id = arr[i];
		if (id != in[x]) continue;
		vector< pair<int, int> > tmp = vec[id]; vec[id].clear();
		for (auto j : tmp) if (j.second != x) vec[id].push_back(j);
		if (!vec[id].size()) {
			arr.erase(arr.begin() + i); break;
		}
		calc(vec[id]); break;
	}
	a[x] = y;
	bool flag = 0;
	for (int i = 0; i < arr.size(); ++i) {
		int id = arr[i];
		if (vec[id].back().first < a[x]) continue;
		flag = 1, in[x] = arr[i], push(i, x); break;
	}
	if (!flag) {
		in[x] = arr.back();
		push(arr.size() - 1, x);
	}
	return get();
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size(); ++i) {
                  ~~^~~~~~~~~~~~
elephants.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size(); ++i) {
                  ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	3832 KB	Output is correct
2	Correct	5 ms	4068 KB	Output is correct
3	Correct	6 ms	4068 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	3832 KB	Output is correct
2	Correct	5 ms	4068 KB	Output is correct
3	Correct	6 ms	4068 KB	Output is correct
4	Correct	8 ms	4068 KB	Output is correct
5	Correct	6 ms	4068 KB	Output is correct
6	Correct	6 ms	4136 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	3832 KB	Output is correct
2	Correct	5 ms	4068 KB	Output is correct
3	Correct	6 ms	4068 KB	Output is correct
4	Correct	8 ms	4068 KB	Output is correct
5	Correct	6 ms	4068 KB	Output is correct
6	Correct	6 ms	4136 KB	Output is correct
7	Correct	821 ms	5460 KB	Output is correct
8	Correct	740 ms	5648 KB	Output is correct
9	Correct	759 ms	7636 KB	Output is correct
10	Correct	758 ms	10036 KB	Output is correct
11	Correct	603 ms	11148 KB	Output is correct
12	Correct	1188 ms	12220 KB	Output is correct
13	Correct	647 ms	13960 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	3832 KB	Output is correct
2	Correct	5 ms	4068 KB	Output is correct
3	Correct	6 ms	4068 KB	Output is correct
4	Correct	8 ms	4068 KB	Output is correct
5	Correct	6 ms	4068 KB	Output is correct
6	Correct	6 ms	4136 KB	Output is correct
7	Correct	821 ms	5460 KB	Output is correct
8	Correct	740 ms	5648 KB	Output is correct
9	Correct	759 ms	7636 KB	Output is correct
10	Correct	758 ms	10036 KB	Output is correct
11	Correct	603 ms	11148 KB	Output is correct
12	Correct	1188 ms	12220 KB	Output is correct
13	Correct	647 ms	13960 KB	Output is correct
14	Correct	825 ms	14748 KB	Output is correct
15	Correct	1130 ms	15616 KB	Output is correct
16	Correct	1968 ms	18500 KB	Output is correct
17	Correct	2177 ms	21316 KB	Output is correct
18	Correct	1975 ms	22968 KB	Output is correct
19	Correct	1063 ms	25220 KB	Output is correct
20	Correct	1956 ms	27524 KB	Output is correct
21	Correct	2318 ms	29320 KB	Output is correct
22	Correct	1192 ms	31620 KB	Output is correct

Subtask #5
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	3832 KB	Output is correct
2	Correct	5 ms	4068 KB	Output is correct
3	Correct	6 ms	4068 KB	Output is correct
4	Correct	8 ms	4068 KB	Output is correct
5	Correct	6 ms	4068 KB	Output is correct
6	Correct	6 ms	4136 KB	Output is correct
7	Correct	821 ms	5460 KB	Output is correct
8	Correct	740 ms	5648 KB	Output is correct
9	Correct	759 ms	7636 KB	Output is correct
10	Correct	758 ms	10036 KB	Output is correct
11	Correct	603 ms	11148 KB	Output is correct
12	Correct	1188 ms	12220 KB	Output is correct
13	Correct	647 ms	13960 KB	Output is correct
14	Correct	825 ms	14748 KB	Output is correct
15	Correct	1130 ms	15616 KB	Output is correct
16	Correct	1968 ms	18500 KB	Output is correct
17	Correct	2177 ms	21316 KB	Output is correct
18	Correct	1975 ms	22968 KB	Output is correct
19	Correct	1063 ms	25220 KB	Output is correct
20	Correct	1956 ms	27524 KB	Output is correct
21	Correct	2318 ms	29320 KB	Output is correct
22	Correct	1192 ms	31620 KB	Output is correct
23	Correct	4329 ms	38540 KB	Output is correct
24	Correct	4407 ms	43568 KB	Output is correct
25	Correct	3301 ms	48592 KB	Output is correct
26	Correct	3797 ms	56148 KB	Output is correct
27	Correct	3766 ms	59700 KB	Output is correct
28	Correct	3063 ms	59700 KB	Output is correct
29	Correct	2942 ms	60608 KB	Output is correct
30	Correct	3256 ms	63528 KB	Output is correct
31	Correct	3053 ms	66464 KB	Output is correct
32	Correct	3343 ms	77304 KB	Output is correct
33	Correct	2790 ms	81036 KB	Output is correct
34	Correct	3918 ms	85760 KB	Output is correct
35	Correct	2384 ms	89452 KB	Output is correct
36	Correct	2507 ms	93948 KB	Output is correct
37	Correct	8025 ms	98360 KB	Output is correct
38	Correct	4161 ms	103712 KB	Output is correct
39	Correct	3100 ms	107176 KB	Output is correct
40	Correct	3589 ms	112000 KB	Output is correct
41	Correct	7155 ms	115292 KB	Output is correct
42	Correct	7211 ms	119752 KB	Output is correct

답안 #62060

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