oj.uz

답안 #761023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
761023 2023-06-19T04:42:13 Z SanguineChameleon 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
50 / 100
 9000 ms 12172 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1.5e5 + 20;
const int block_size = 10000;
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7376 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 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 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7376 KB Output is correct
7 Correct 3130 ms 8508 KB Output is correct
8 Correct 4524 ms 8980 KB Output is correct
9 Correct 1965 ms 9188 KB Output is correct
10 Correct 3696 ms 11972 KB Output is correct
11 Correct 3904 ms 12024 KB Output is correct
12 Correct 3839 ms 9592 KB Output is correct
13 Correct 3561 ms 12172 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 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 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7376 KB Output is correct
7 Correct 3130 ms 8508 KB Output is correct
8 Correct 4524 ms 8980 KB Output is correct
9 Correct 1965 ms 9188 KB Output is correct
10 Correct 3696 ms 11972 KB Output is correct
11 Correct 3904 ms 12024 KB Output is correct
12 Correct 3839 ms 9592 KB Output is correct
13 Correct 3561 ms 12172 KB Output is correct
14 Correct 2691 ms 9192 KB Output is correct
15 Correct 5767 ms 8676 KB Output is correct
16 Execution timed out 9007 ms 9520 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 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 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7376 KB Output is correct
7 Correct 3130 ms 8508 KB Output is correct
8 Correct 4524 ms 8980 KB Output is correct
9 Correct 1965 ms 9188 KB Output is correct
10 Correct 3696 ms 11972 KB Output is correct
11 Correct 3904 ms 12024 KB Output is correct
12 Correct 3839 ms 9592 KB Output is correct
13 Correct 3561 ms 12172 KB Output is correct
14 Correct 2691 ms 9192 KB Output is correct
15 Correct 5767 ms 8676 KB Output is correct
16 Execution timed out 9007 ms 9520 KB Time limit exceeded
17 Halted 0 ms 0 KB -