oj.uz

Submission #227470

# Submission time Handle Problem Language Result Execution time Memory
227470 2020-04-27T13:52:22 Z spdskatr Dancing Elephants (IOI11_elephants) C++14
100 / 100
 7245 ms 14944 KB 
// This problem is cooked
#include "elephants.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cassert>
#define fi first
#define se second
#define K 404 // Not found

using namespace std;
typedef pair<int, int> pii;
int N, L, cnt, loc[150005], curblock[150005];
pair<int, int> el[150005];

struct block {
	int val[K<<1], pos[K<<1], dp[K<<1], ext[K<<1], sz;
	void reset() {
		fill(val, val+K, 0);
		fill(dp, dp+K, 0);
	}
	void recalc() {
		int rp = sz;
		for (int i = sz - 1; i >= 0; i--) {
			while (pos[rp-1] > pos[i] + L) rp--;
			if (rp == sz) {
				dp[i] = 1;
				ext[i] = pos[i] + L + 1;
			} else {
				dp[i] = dp[rp] + 1;
				ext[i] = ext[rp];
			}
		}
	}
	void remove(int x) {
		int lp = 0;
		while (val[lp] != x && lp < sz) lp++;
		assert(val[lp] == x);
		sz--;
		while (lp < sz) {
			val[lp] = val[lp+1];
			pos[lp] = pos[lp+1];
			lp++;
		}
		val[sz] = pos[sz] = 0;
		recalc();
	}
	void insert(int x, int v) {
		int lp = 0;
		while (lp < sz && pos[lp] < v) lp++;
		sz++;
		for (int i = sz-1; i > lp; i--) {
			val[i] = val[i-1];
			pos[i] = pos[i-1];
		}
		val[lp] = x, pos[lp] = v;
		recalc();
	}
} sd[505];

void init(int n, int l, int X[])
{
	N = n, L = l;
	for (int i = 0; i < N; i++) loc[i] = X[i];
	for (int b = 0; b * K < N; b++) {
		for (int j = 0; j < min(K, N-b*K); j++) {
			int actual = b*K+j;
			sd[b].val[j] = actual;
			sd[b].pos[j] = loc[actual];
			curblock[actual] = b;
		}
		sd[b].sz = min(K, N-b*K);
		sd[b].recalc();
	}
}

int update(int ind, int y)
{
	loc[ind] = y;
	if (cnt >= K - 1) {
		// Recalculate everything
		for (int i = 0; i < N; i++) el[i] = { loc[i], i };
		sort(el, el+N);
		for (int b = 0; b*K < N; b++) {
			sd[b].reset();
			for (int j = 0; j < min(K, N-b*K); j++) {
				int actual = b*K + j;
				sd[b].val[j] = el[actual].se;
				sd[b].pos[j] = el[actual].fi;
				curblock[el[actual].se] = b;
			}
			sd[b].sz = min(K, N-b*K);
			sd[b].recalc();
		}
		cnt = 0;
	} else {
		int b2 = 0;
		sd[curblock[ind]].remove(ind);
		while ((b2 + 1) * K < N && sd[b2+1].sz > 0 && sd[b2+1].pos[0] < loc[ind]) {
			b2++;
		}
		curblock[ind] = b2;
		sd[b2].insert(ind, loc[ind]);
	}
	int curpt = 0, tot = 0;
	for (int b = 0; (b+1)*K < N || (b*K < N && sd[b].sz > 0); b++) {
		if (sd[b].pos[sd[b].sz-1] >= curpt) {
			int lo = 0, hi = sd[b].sz;
			if (sd[b].pos[0] >= curpt) hi = 0;
			else while (lo + 1 < hi) {
				int mid = (lo + hi) / 2;
				if (sd[b].pos[mid] < curpt) lo = mid;
				else hi = mid;
			}
			tot += sd[b].dp[hi];
			curpt = sd[b].ext[hi];
			assert(curpt > sd[b].pos[sd[b].sz-1]);
		}
	}
	cnt++;
	return tot;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 268 ms 2600 KB Output is correct
8 Correct 285 ms 2936 KB Output is correct
9 Correct 356 ms 5068 KB Output is correct
10 Correct 498 ms 4984 KB Output is correct
11 Correct 519 ms 4728 KB Output is correct
12 Correct 964 ms 4964 KB Output is correct
13 Correct 541 ms 4728 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 268 ms 2600 KB Output is correct
8 Correct 285 ms 2936 KB Output is correct
9 Correct 356 ms 5068 KB Output is correct
10 Correct 498 ms 4984 KB Output is correct
11 Correct 519 ms 4728 KB Output is correct
12 Correct 964 ms 4964 KB Output is correct
13 Correct 541 ms 4728 KB Output is correct
14 Correct 446 ms 3648 KB Output is correct
15 Correct 478 ms 3824 KB Output is correct
16 Correct 1519 ms 5624 KB Output is correct
17 Correct 1724 ms 6904 KB Output is correct
18 Correct 1890 ms 6776 KB Output is correct
19 Correct 1010 ms 6964 KB Output is correct
20 Correct 1676 ms 6904 KB Output is correct
21 Correct 1699 ms 6904 KB Output is correct
22 Correct 958 ms 6392 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 268 ms 2600 KB Output is correct
8 Correct 285 ms 2936 KB Output is correct
9 Correct 356 ms 5068 KB Output is correct
10 Correct 498 ms 4984 KB Output is correct
11 Correct 519 ms 4728 KB Output is correct
12 Correct 964 ms 4964 KB Output is correct
13 Correct 541 ms 4728 KB Output is correct
14 Correct 446 ms 3648 KB Output is correct
15 Correct 478 ms 3824 KB Output is correct
16 Correct 1519 ms 5624 KB Output is correct
17 Correct 1724 ms 6904 KB Output is correct
18 Correct 1890 ms 6776 KB Output is correct
19 Correct 1010 ms 6964 KB Output is correct
20 Correct 1676 ms 6904 KB Output is correct
21 Correct 1699 ms 6904 KB Output is correct
22 Correct 958 ms 6392 KB Output is correct
23 Correct 3321 ms 14840 KB Output is correct
24 Correct 3951 ms 14812 KB Output is correct
25 Correct 2437 ms 14820 KB Output is correct
26 Correct 4566 ms 14840 KB Output is correct
27 Correct 4989 ms 14684 KB Output is correct
28 Correct 1437 ms 5324 KB Output is correct
29 Correct 1341 ms 5328 KB Output is correct
30 Correct 1402 ms 5368 KB Output is correct
31 Correct 1327 ms 5368 KB Output is correct
32 Correct 3943 ms 14248 KB Output is correct
33 Correct 3544 ms 13688 KB Output is correct
34 Correct 3871 ms 14456 KB Output is correct
35 Correct 3873 ms 14944 KB Output is correct
36 Correct 2309 ms 14328 KB Output is correct
37 Correct 6743 ms 14640 KB Output is correct
38 Correct 4494 ms 13476 KB Output is correct
39 Correct 4306 ms 14584 KB Output is correct
40 Correct 4541 ms 13488 KB Output is correct
41 Correct 6955 ms 14328 KB Output is correct
42 Correct 7245 ms 14468 KB Output is correct