oj.uz

Submission #761019

# Submission time Handle Problem Language Result Execution time Memory
761019 2023-06-19T04:31:21 Z SanguineChameleon Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 19476 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1.5e5 + 20;
const int block_size = 400;
vector<int> pos[maxN];
vector<pair<int, int>> dp[maxN];
int A[maxN];
int N, L;
int block_cnt;

void calc_block(int id) {
	vector<int> &pos_block = pos[id];
	vector<pair<int, int>> &dp_block = dp[id];
	int sz = pos_block.size();
	dp_block.resize(sz);
	int rt = sz;
	for (int i = sz - 1; i >= 0; i--) {
		while (pos_block[rt - 1] > pos_block[i] + L) {
			rt--;
		}
		if (rt == sz) {
			dp_block[i].first = 1;
			dp_block[i].second = pos_block[i];
		}
		else {
			dp_block[i].first = dp_block[rt].first + 1;
			dp_block[i].second = dp_block[rt].second;
		}
	}
}

int calc_all() {
	int res = dp[0][0].first;
	int last = dp[0][0].second;
	for (int id = 1; id < block_cnt; id++) {
		if (pos[id].back() > last + L) {
			int i = upper_bound(pos[id].begin(), pos[id].end(), last + L) - pos[id].begin();
			res += dp[id][i].first;
			last = dp[id][i].second;
		}
	}
	return res;
}

void rem(int X) {
	int id = 0;
	while (pos[id].back() < X) {
		id++;
	}
	pos[id].erase(lower_bound(pos[id].begin(), pos[id].end(), X));
	if (pos[id].empty()) {
		for (int i = id + 1; i < block_cnt; i++) {
			swap(pos[i - 1], pos[i]);
			swap(dp[i - 1], dp[i]);
		}
		block_cnt--;
	}
	else {
		calc_block(id);
	}
}

void add(int X) {
	int id = 0;
	while (id < block_cnt && pos[id].back() < X) {
		id++;
	}
	if (id == block_cnt) {
		block_cnt++;
	}
	pos[id].insert(upper_bound(pos[id].begin(), pos[id].end(), X), X);
	if ((int)pos[id].size() == block_size * 2) {
		for (int i = block_cnt - 1; i > id; i--) {
			swap(pos[i + 1], pos[i]);
			swap(dp[i + 1], dp[i]);
		}
		pos[id + 1].insert(pos[id + 1].begin(), pos[id].begin() + block_size, pos[id].end());
		pos[id].erase(pos[id].begin() + block_size, pos[id].end());
		block_cnt++;
		calc_block(id);
		calc_block(id + 1);
	}
	else {
		calc_block(id);
	}
}

void init(int _N, int _L, int _A[]) {
	N = _N;
	L = _L;
	block_cnt = (N - 1) / block_size + 1;
	for (int i = 0; i < N; i++) {
		A[i] = _A[i];
		pos[i / block_size].push_back(A[i]);
	}
	for (int id = 0; id < block_cnt; id++) {
		calc_block(id);
	}
}

int update(int i, int X) {
	rem(A[i]);
	A[i] = X;
	add(A[i]);
	return calc_all();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 3 ms 7356 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 3 ms 7356 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 3 ms 7356 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 135 ms 9144 KB Output is correct
8 Correct 147 ms 9348 KB Output is correct
9 Correct 164 ms 10936 KB Output is correct
10 Correct 3147 ms 13584 KB Output is correct
11 Correct 3496 ms 13364 KB Output is correct
12 Correct 278 ms 10796 KB Output is correct
13 Correct 3149 ms 13152 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 3 ms 7356 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 135 ms 9144 KB Output is correct
8 Correct 147 ms 9348 KB Output is correct
9 Correct 164 ms 10936 KB Output is correct
10 Correct 3147 ms 13584 KB Output is correct
11 Correct 3496 ms 13364 KB Output is correct
12 Correct 278 ms 10796 KB Output is correct
13 Correct 3149 ms 13152 KB Output is correct
14 Correct 166 ms 10444 KB Output is correct
15 Correct 229 ms 10268 KB Output is correct
16 Correct 548 ms 11436 KB Output is correct
17 Correct 518 ms 12516 KB Output is correct
18 Correct 526 ms 11976 KB Output is correct
19 Correct 245 ms 11724 KB Output is correct
20 Correct 521 ms 12408 KB Output is correct
21 Correct 444 ms 12152 KB Output is correct
22 Correct 6195 ms 15572 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 3 ms 7356 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 135 ms 9144 KB Output is correct
8 Correct 147 ms 9348 KB Output is correct
9 Correct 164 ms 10936 KB Output is correct
10 Correct 3147 ms 13584 KB Output is correct
11 Correct 3496 ms 13364 KB Output is correct
12 Correct 278 ms 10796 KB Output is correct
13 Correct 3149 ms 13152 KB Output is correct
14 Correct 166 ms 10444 KB Output is correct
15 Correct 229 ms 10268 KB Output is correct
16 Correct 548 ms 11436 KB Output is correct
17 Correct 518 ms 12516 KB Output is correct
18 Correct 526 ms 11976 KB Output is correct
19 Correct 245 ms 11724 KB Output is correct
20 Correct 521 ms 12408 KB Output is correct
21 Correct 444 ms 12152 KB Output is correct
22 Correct 6195 ms 15572 KB Output is correct
23 Correct 1152 ms 18068 KB Output is correct
24 Correct 1235 ms 18072 KB Output is correct
25 Correct 845 ms 17948 KB Output is correct
26 Execution timed out 9072 ms 19476 KB Time limit exceeded
27 Halted 0 ms 0 KB -