oj.uz

Submission #105399

# Submission time Handle Problem Language Result Execution time Memory
105399 2019-04-11T20:50:58 Z eriksuenderhauf Dancing Elephants (IOI11_elephants) C++11
100 / 100
 3092 ms 26572 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 = 513;
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 1 ms 384 KB Output is correct
5 Correct 3 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 1 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 298 ms 5088 KB Output is correct
8 Correct 291 ms 5752 KB Output is correct
9 Correct 371 ms 7552 KB Output is correct
10 Correct 366 ms 8760 KB Output is correct
11 Correct 402 ms 8824 KB Output is correct
12 Correct 754 ms 9060 KB Output is correct
13 Correct 403 ms 8696 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 1 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 298 ms 5088 KB Output is correct
8 Correct 291 ms 5752 KB Output is correct
9 Correct 371 ms 7552 KB Output is correct
10 Correct 366 ms 8760 KB Output is correct
11 Correct 402 ms 8824 KB Output is correct
12 Correct 754 ms 9060 KB Output is correct
13 Correct 403 ms 8696 KB Output is correct
14 Correct 199 ms 5752 KB Output is correct
15 Correct 403 ms 7636 KB Output is correct
16 Correct 871 ms 10232 KB Output is correct
17 Correct 955 ms 12024 KB Output is correct
18 Correct 1034 ms 12152 KB Output is correct
19 Correct 607 ms 12592 KB Output is correct
20 Correct 1046 ms 12376 KB Output is correct
21 Correct 1028 ms 12412 KB Output is correct
22 Correct 585 ms 12024 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 1 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 298 ms 5088 KB Output is correct
8 Correct 291 ms 5752 KB Output is correct
9 Correct 371 ms 7552 KB Output is correct
10 Correct 366 ms 8760 KB Output is correct
11 Correct 402 ms 8824 KB Output is correct
12 Correct 754 ms 9060 KB Output is correct
13 Correct 403 ms 8696 KB Output is correct
14 Correct 199 ms 5752 KB Output is correct
15 Correct 403 ms 7636 KB Output is correct
16 Correct 871 ms 10232 KB Output is correct
17 Correct 955 ms 12024 KB Output is correct
18 Correct 1034 ms 12152 KB Output is correct
19 Correct 607 ms 12592 KB Output is correct
20 Correct 1046 ms 12376 KB Output is correct
21 Correct 1028 ms 12412 KB Output is correct
22 Correct 585 ms 12024 KB Output is correct
23 Correct 2515 ms 24056 KB Output is correct
24 Correct 2015 ms 23464 KB Output is correct
25 Correct 2072 ms 22260 KB Output is correct
26 Correct 2079 ms 26572 KB Output is correct
27 Correct 2224 ms 26392 KB Output is correct
28 Correct 2178 ms 10072 KB Output is correct
29 Correct 1883 ms 9692 KB Output is correct
30 Correct 2124 ms 10204 KB Output is correct
31 Correct 1886 ms 9468 KB Output is correct
32 Correct 2571 ms 26100 KB Output is correct
33 Correct 1106 ms 18296 KB Output is correct
34 Correct 1737 ms 26236 KB Output is correct
35 Correct 759 ms 19448 KB Output is correct
36 Correct 68 ms 8444 KB Output is correct
37 Correct 1166 ms 19436 KB Output is correct
38 Correct 2168 ms 25384 KB Output is correct
39 Correct 2143 ms 26532 KB Output is correct
40 Correct 2035 ms 25356 KB Output is correct
41 Correct 2917 ms 25264 KB Output is correct
42 Correct 3092 ms 25836 KB Output is correct