oj.uz

Submission #103916

# Submission time Handle Problem Language Result Execution time Memory
103916 2019-04-03T09:02:36 Z KCSC Dancing Elephants (IOI11_elephants) C++14
100 / 100
 7091 ms 15304 KB 
// 8.45
#ifndef HOME
	#include "elephants.h"
#endif
#include <bits/stdc++.h>
using namespace std;

	const int DIM = 160005;
	const int SQRT = 1005;
	const int INF = 1000000005;

int n, l;

pair<int, int> ele[DIM], iele[DIM];
vector<pair<int, int>> buc[DIM / SQRT];

int cnt[DIM / SQRT][SQRT * 2]; 
int nxt[DIM / SQRT][SQRT * 2], whb[DIM];

void updateDp(int b) {
	int s = (int) buc[b].size();
	for (int i = s - 1; i >= 1; --i) {
		if (buc[b][i - 1] > buc[b][i]) {
			swap(buc[b][i - 1], buc[b][i]); }
		else {
			break; } }	
	for (int i = 0; i < s; ++i) {
		whb[buc[b][i].second] = b; }
	for (int i = s - 1, j = s; i >= 0; --i) {
		while (buc[b][j - 1].first > buc[b][i].first + l) {
			--j; }
		if (j == s) {
			cnt[b][i] = 1; 
			nxt[b][i] = buc[b][i].first + l; }
		else {
			cnt[b][i] = 1 + cnt[b][j]; 
			nxt[b][i] = nxt[b][j]; } } }

void resetDp(void) {
	for (int i = 0; i < n; ++i) {
		ele[i] = iele[i]; }
	sort(ele, ele + n);
	for (int i = 0; i < n; ++i) {
		if (i % SQRT == 0) {
			buc[i / SQRT].clear(); }
		buc[i / SQRT].push_back(ele[i]); }
	for (int i = 0; i * SQRT < n; ++i) {
		updateDp(i); } }

void init(int _n, int _l, int *X) {
	n = _n; l = _l;
	for (int i = 0; i < n; ++i) {
		iele[i] = make_pair(X[i], i); }
	iele[n] = make_pair(-INF, n); ++n;
	while (n % SQRT != 0) {
		iele[n] = make_pair(-INF, n); ++n; }
	resetDp(); }

int query(void) {
	int ans = 0;
	for (int i = 0, v = -INF; i * SQRT < n; ++i) {
		if (prev(buc[i].end()) -> first < v) {
			continue; }
		auto it = lower_bound(buc[i].begin(), buc[i].end(), make_pair(v, 0)) - buc[i].begin();
		ans += cnt[i][it]; v = nxt[i][it] + 1; }
	return ans; }
	
int update(int x, int c) {
	static int nr = 0; 
	if (++nr == SQRT - 2) {
		iele[x].first = c; resetDp(); nr = 0; }
	else {
		int wb = whb[x], ps = iele[x].first; iele[x].first = c;
		buc[wb].erase(lower_bound(buc[wb].begin(), buc[wb].end(), make_pair(ps, x))); updateDp(wb);
		if (prev(buc[n / SQRT - 1].end()) -> first <= c) {
			buc[n / SQRT - 1].push_back(make_pair(c, x)); updateDp(n / SQRT - 1); }
		else {
			for (int i = 0; i * SQRT < n; ++i) {
				if (buc[i].begin() -> first <= c and (prev(buc[i].end()) -> first >= c or buc[i + 1].begin() -> first >= c)) {
					buc[i].push_back(make_pair(c, x)); updateDp(i); break; } } } }
	return query() - 1; }

#ifdef HOME
int main(void) {
	freopen("elephants.in", "r", stdin);
	freopen("elephants.out", "w", stdout);
	int N, L, M; cin >> N >> L >> M;
	int *X = new int[N];
	for (int i = 0; i < N; ++i) {
		cin >> X[i]; }
	init(N, L, X); int h = 0;
	while (M--) {
		int x, y, v; cin >> x >> y >> v; ++h;
		int u = update(x, y);
		if (update(x, y) != v) {	
			cout << h << " " << u << " " << v; return 0; } }
	cout << "True"; 
	return 0; }
#endif

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 480 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 533 ms 1536 KB Output is correct
8 Correct 661 ms 1868 KB Output is correct
9 Correct 708 ms 3320 KB Output is correct
10 Correct 578 ms 3320 KB Output is correct
11 Correct 671 ms 4728 KB Output is correct
12 Correct 1289 ms 5112 KB Output is correct
13 Correct 656 ms 4584 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 480 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 533 ms 1536 KB Output is correct
8 Correct 661 ms 1868 KB Output is correct
9 Correct 708 ms 3320 KB Output is correct
10 Correct 578 ms 3320 KB Output is correct
11 Correct 671 ms 4728 KB Output is correct
12 Correct 1289 ms 5112 KB Output is correct
13 Correct 656 ms 4584 KB Output is correct
14 Correct 703 ms 3804 KB Output is correct
15 Correct 852 ms 3804 KB Output is correct
16 Correct 2214 ms 5624 KB Output is correct
17 Correct 2259 ms 6904 KB Output is correct
18 Correct 2374 ms 6764 KB Output is correct
19 Correct 1078 ms 6776 KB Output is correct
20 Correct 2174 ms 6876 KB Output is correct
21 Correct 1982 ms 6904 KB Output is correct
22 Correct 973 ms 6264 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 480 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 533 ms 1536 KB Output is correct
8 Correct 661 ms 1868 KB Output is correct
9 Correct 708 ms 3320 KB Output is correct
10 Correct 578 ms 3320 KB Output is correct
11 Correct 671 ms 4728 KB Output is correct
12 Correct 1289 ms 5112 KB Output is correct
13 Correct 656 ms 4584 KB Output is correct
14 Correct 703 ms 3804 KB Output is correct
15 Correct 852 ms 3804 KB Output is correct
16 Correct 2214 ms 5624 KB Output is correct
17 Correct 2259 ms 6904 KB Output is correct
18 Correct 2374 ms 6764 KB Output is correct
19 Correct 1078 ms 6776 KB Output is correct
20 Correct 2174 ms 6876 KB Output is correct
21 Correct 1982 ms 6904 KB Output is correct
22 Correct 973 ms 6264 KB Output is correct
23 Correct 5191 ms 14248 KB Output is correct
24 Correct 5459 ms 14328 KB Output is correct
25 Correct 4258 ms 14200 KB Output is correct
26 Correct 3579 ms 14316 KB Output is correct
27 Correct 3400 ms 14160 KB Output is correct
28 Correct 3167 ms 5496 KB Output is correct
29 Correct 3239 ms 5624 KB Output is correct
30 Correct 3203 ms 5464 KB Output is correct
31 Correct 3029 ms 5368 KB Output is correct
32 Correct 4021 ms 13800 KB Output is correct
33 Correct 3210 ms 13176 KB Output is correct
34 Correct 3271 ms 14072 KB Output is correct
35 Correct 2829 ms 14272 KB Output is correct
36 Correct 4530 ms 13816 KB Output is correct
37 Correct 6833 ms 15304 KB Output is correct
38 Correct 3418 ms 12972 KB Output is correct
39 Correct 3316 ms 13944 KB Output is correct
40 Correct 3599 ms 13176 KB Output is correct
41 Correct 6859 ms 14164 KB Output is correct
42 Correct 7091 ms 14288 KB Output is correct