oj.uz

Submission #105400

# Submission time Handle Problem Language Result Execution time Memory
105400 2019-04-11T21:05:14 Z eriksuenderhauf Dancing Elephants (IOI11_elephants) C++11
100 / 100
 3128 ms 21704 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "elephants.h"
//#include "grader.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long int ll;
const int INF = 1e9 + 7;
const int MAXN = 15e4 + 5;
const int BLOCK = 470;
int n, l, a[MAXN], b[MAXN], st[BLOCK];
int bcnt = 1, buc[BLOCK][2 * BLOCK + 1];
int val[BLOCK][2 * BLOCK + 1][2];
map<int,int> cnt;

void calc(int ind) {
	int sz = buc[ind][0];
	for (int i = sz; i > 0; i--) {
		while (sz > 0 && buc[ind][i] + l < buc[ind][sz]) 
			sz--;
		if (sz < buc[ind][0]) {
			val[ind][i][0] = val[ind][sz + 1][0] + 1;
			val[ind][i][1] = val[ind][sz + 1][1];
		} else {
			val[ind][i][0] = 1;
			val[ind][i][1] = buc[ind][i];
		}
	}
}

void build() {
	bcnt = 0;
	for (int i = 0; i * BLOCK < n; i++) {
		bcnt++;
		buc[i][0] = 0;
		for (int j = 0; j < BLOCK && BLOCK * i + j < n; j++)
			buc[i][++buc[i][0]] = b[BLOCK * i + j];
		calc(i);
		st[i] = buc[i][1];
	}
}

void init(int N, int L, int X[]) {
	n = N, l = L;
	for (int i = 0; i < n; i++) {
		a[i] = X[i], b[i] = X[i];
		cnt[X[i]]++;
	}
	n = unique(b, b + n) - b;
	build();
}

void restore() {
	int cur = 0;
	for (int i = 0; i < bcnt; i++)
		for (int j = 1; j <= buc[i][0]; j++)
			b[cur++] = buc[i][j];
}

int getBucket(int pos) {
	return lower_bound(st + 1, st + bcnt, pos + 1) - st - 1;
}

int update(int ind, int pos) {
	cnt[a[ind]]--;
	if (cnt[a[ind]] == 0) {
		int b = getBucket(a[ind]);
		int s = lower_bound(buc[b] + 1, buc[b] + buc[b][0] + 1, a[ind]) - buc[b];
		for (int i = s; i < buc[b][0]; i++)
			buc[b][i] = buc[b][i + 1];
		n--, buc[b][0]--;
		calc(b);
	}
	cnt[pos]++;
	if (cnt[pos] == 1) {
		int b = getBucket(pos);
		if (buc[b][0] == 2 * BLOCK) {
			restore();
			build();
			b = getBucket(pos);
		}
		int s = lower_bound(buc[b] + 1, buc[b] + buc[b][0] + 1, pos) - buc[b];
		for (int i = buc[b][0] + 1; i > s; i--)
			buc[b][i] = buc[b][i - 1];
		buc[b][s] = pos;
		n++, buc[b][0]++;
		calc(b);
	}
	a[ind] = pos;
	int ret = 0, cur = -INF;
	for (int i = 0; i < bcnt; i++) {
		int nx = lower_bound(buc[i] + 1, buc[i] + buc[i][0] + 1, cur + l + 1) - buc[i];
		if (nx > buc[i][0]) continue; // picture ends in the next bucket
		ret += val[i][nx][0];
		cur = val[i][nx][1];
	}
	return ret;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 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 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 385 ms 4336 KB Output is correct
8 Correct 330 ms 4564 KB Output is correct
9 Correct 407 ms 6068 KB Output is correct
10 Correct 355 ms 7388 KB Output is correct
11 Correct 403 ms 7464 KB Output is correct
12 Correct 664 ms 7544 KB Output is correct
13 Correct 413 ms 7496 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 385 ms 4336 KB Output is correct
8 Correct 330 ms 4564 KB Output is correct
9 Correct 407 ms 6068 KB Output is correct
10 Correct 355 ms 7388 KB Output is correct
11 Correct 403 ms 7464 KB Output is correct
12 Correct 664 ms 7544 KB Output is correct
13 Correct 413 ms 7496 KB Output is correct
14 Correct 238 ms 4316 KB Output is correct
15 Correct 501 ms 6320 KB Output is correct
16 Correct 987 ms 8024 KB Output is correct
17 Correct 1028 ms 9988 KB Output is correct
18 Correct 1077 ms 10204 KB Output is correct
19 Correct 694 ms 10256 KB Output is correct
20 Correct 1099 ms 10360 KB Output is correct
21 Correct 1014 ms 10388 KB Output is correct
22 Correct 660 ms 10276 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 385 ms 4336 KB Output is correct
8 Correct 330 ms 4564 KB Output is correct
9 Correct 407 ms 6068 KB Output is correct
10 Correct 355 ms 7388 KB Output is correct
11 Correct 403 ms 7464 KB Output is correct
12 Correct 664 ms 7544 KB Output is correct
13 Correct 413 ms 7496 KB Output is correct
14 Correct 238 ms 4316 KB Output is correct
15 Correct 501 ms 6320 KB Output is correct
16 Correct 987 ms 8024 KB Output is correct
17 Correct 1028 ms 9988 KB Output is correct
18 Correct 1077 ms 10204 KB Output is correct
19 Correct 694 ms 10256 KB Output is correct
20 Correct 1099 ms 10360 KB Output is correct
21 Correct 1014 ms 10388 KB Output is correct
22 Correct 660 ms 10276 KB Output is correct
23 Correct 2517 ms 19184 KB Output is correct
24 Correct 2373 ms 18516 KB Output is correct
25 Correct 1990 ms 17416 KB Output is correct
26 Correct 2313 ms 21624 KB Output is correct
27 Correct 2338 ms 21480 KB Output is correct
28 Correct 1994 ms 7044 KB Output is correct
29 Correct 1876 ms 6568 KB Output is correct
30 Correct 1944 ms 7136 KB Output is correct
31 Correct 1818 ms 6648 KB Output is correct
32 Correct 2702 ms 21684 KB Output is correct
33 Correct 1185 ms 14584 KB Output is correct
34 Correct 1921 ms 21704 KB Output is correct
35 Correct 778 ms 14456 KB Output is correct
36 Correct 67 ms 3832 KB Output is correct
37 Correct 1472 ms 14460 KB Output is correct
38 Correct 1909 ms 21628 KB Output is correct
39 Correct 2271 ms 21500 KB Output is correct
40 Correct 2025 ms 21632 KB Output is correct
41 Correct 3128 ms 20984 KB Output is correct
42 Correct 2997 ms 20984 KB Output is correct