oj.uz

Submission #62060

# Submission time Handle Problem Language Result Execution time Memory
62060 2018-07-27T10:58:57 Z aome Dancing Elephants (IOI11_elephants) C++17
100 / 100
 8025 ms 119752 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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