oj.uz

Submission #105401

# Submission time Handle Problem Language Result Execution time Memory
105401 2019-04-11T21:06:51 Z eriksuenderhauf Dancing Elephants (IOI11_elephants) C++11
100 / 100
 2931 ms 21708 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 3 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 3 ms 384 KB Output is correct
4 Correct 2 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 3 ms 384 KB Output is correct
4 Correct 2 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 388 ms 4288 KB Output is correct
8 Correct 399 ms 4856 KB Output is correct
9 Correct 385 ms 5972 KB Output is correct
10 Correct 447 ms 7416 KB Output is correct
11 Correct 420 ms 7516 KB Output is correct
12 Correct 809 ms 7416 KB Output is correct
13 Correct 347 ms 7492 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 3 ms 384 KB Output is correct
4 Correct 2 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 388 ms 4288 KB Output is correct
8 Correct 399 ms 4856 KB Output is correct
9 Correct 385 ms 5972 KB Output is correct
10 Correct 447 ms 7416 KB Output is correct
11 Correct 420 ms 7516 KB Output is correct
12 Correct 809 ms 7416 KB Output is correct
13 Correct 347 ms 7492 KB Output is correct
14 Correct 241 ms 4348 KB Output is correct
15 Correct 577 ms 6344 KB Output is correct
16 Correct 993 ms 8156 KB Output is correct
17 Correct 1168 ms 10092 KB Output is correct
18 Correct 1217 ms 10180 KB Output is correct
19 Correct 631 ms 10308 KB Output is correct
20 Correct 1237 ms 10424 KB Output is correct
21 Correct 1121 ms 10444 KB Output is correct
22 Correct 605 ms 10264 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 3 ms 384 KB Output is correct
4 Correct 2 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 388 ms 4288 KB Output is correct
8 Correct 399 ms 4856 KB Output is correct
9 Correct 385 ms 5972 KB Output is correct
10 Correct 447 ms 7416 KB Output is correct
11 Correct 420 ms 7516 KB Output is correct
12 Correct 809 ms 7416 KB Output is correct
13 Correct 347 ms 7492 KB Output is correct
14 Correct 241 ms 4348 KB Output is correct
15 Correct 577 ms 6344 KB Output is correct
16 Correct 993 ms 8156 KB Output is correct
17 Correct 1168 ms 10092 KB Output is correct
18 Correct 1217 ms 10180 KB Output is correct
19 Correct 631 ms 10308 KB Output is correct
20 Correct 1237 ms 10424 KB Output is correct
21 Correct 1121 ms 10444 KB Output is correct
22 Correct 605 ms 10264 KB Output is correct
23 Correct 2554 ms 19048 KB Output is correct
24 Correct 2324 ms 18416 KB Output is correct
25 Correct 2023 ms 17400 KB Output is correct
26 Correct 2271 ms 21652 KB Output is correct
27 Correct 2300 ms 21520 KB Output is correct
28 Correct 2360 ms 7276 KB Output is correct
29 Correct 2193 ms 6680 KB Output is correct
30 Correct 2424 ms 7080 KB Output is correct
31 Correct 2248 ms 6632 KB Output is correct
32 Correct 2860 ms 21568 KB Output is correct
33 Correct 1198 ms 14588 KB Output is correct
34 Correct 1881 ms 21708 KB Output is correct
35 Correct 893 ms 14512 KB Output is correct
36 Correct 73 ms 3960 KB Output is correct
37 Correct 1290 ms 14432 KB Output is correct
38 Correct 2004 ms 21520 KB Output is correct
39 Correct 2152 ms 21624 KB Output is correct
40 Correct 2186 ms 21564 KB Output is correct
41 Correct 2931 ms 20888 KB Output is correct
42 Correct 2794 ms 21020 KB Output is correct