oj.uz

Submission #761020

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

const int maxN = 1.5e5 + 20;
const int block_size = 1000;
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 3 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 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 3 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 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 281 ms 8248 KB Output is correct
8 Correct 282 ms 8276 KB Output is correct
9 Correct 241 ms 8984 KB Output is correct
10 Correct 3145 ms 12024 KB Output is correct
11 Correct 3524 ms 11964 KB Output is correct
12 Correct 521 ms 9364 KB Output is correct
13 Correct 3095 ms 12032 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 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 281 ms 8248 KB Output is correct
8 Correct 282 ms 8276 KB Output is correct
9 Correct 241 ms 8984 KB Output is correct
10 Correct 3145 ms 12024 KB Output is correct
11 Correct 3524 ms 11964 KB Output is correct
12 Correct 521 ms 9364 KB Output is correct
13 Correct 3095 ms 12032 KB Output is correct
14 Correct 333 ms 8892 KB Output is correct
15 Correct 423 ms 8788 KB Output is correct
16 Correct 1138 ms 9676 KB Output is correct
17 Correct 943 ms 10444 KB Output is correct
18 Correct 983 ms 9988 KB Output is correct
19 Correct 338 ms 9580 KB Output is correct
20 Correct 920 ms 10340 KB Output is correct
21 Correct 797 ms 10184 KB Output is correct
22 Correct 6158 ms 13872 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 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 281 ms 8248 KB Output is correct
8 Correct 282 ms 8276 KB Output is correct
9 Correct 241 ms 8984 KB Output is correct
10 Correct 3145 ms 12024 KB Output is correct
11 Correct 3524 ms 11964 KB Output is correct
12 Correct 521 ms 9364 KB Output is correct
13 Correct 3095 ms 12032 KB Output is correct
14 Correct 333 ms 8892 KB Output is correct
15 Correct 423 ms 8788 KB Output is correct
16 Correct 1138 ms 9676 KB Output is correct
17 Correct 943 ms 10444 KB Output is correct
18 Correct 983 ms 9988 KB Output is correct
19 Correct 338 ms 9580 KB Output is correct
20 Correct 920 ms 10340 KB Output is correct
21 Correct 797 ms 10184 KB Output is correct
22 Correct 6158 ms 13872 KB Output is correct
23 Correct 1400 ms 12724 KB Output is correct
24 Correct 1718 ms 12800 KB Output is correct
25 Correct 888 ms 12520 KB Output is correct
26 Execution timed out 9011 ms 14388 KB Time limit exceeded
27 Halted 0 ms 0 KB -