oj.uz

Submission #43762

# Submission time Handle Problem Language Result Execution time Memory
43762 2018-03-22T18:34:01 Z baactree Dancing Elephants (IOI11_elephants) C++14
100 / 100
 4352 ms 83804 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
int n, l;
struct group {
	int sz;
	int arr[1005],cnt[1005],last[1005];
	group() :sz(0){}
	void improve() {
		for (int i = sz - 1, k = sz - 1; i >= 0; i--) {
			if (arr[i] + l >= arr[k]) {
				cnt[i] = 1;
				last[i] = arr[i] + l;
			}
			else {
				while (arr[i] + l < arr[k-1])k--;
				cnt[i] = cnt[k] + 1;
				last[i] = last[k];
			}
		}
	}
};
int x[150005],t[150005];
int cnt, sz;
group g[505];
int gg;
void init(int N, int L, int X[]){
	n = N; l = L;
	for (int i = 0; i < n; i++) 
		x[i] = X[i];
	cnt = 0;
	sz = sqrt(n) + 1;
	gg = (n + sz - 1) / sz;
	for (int i = 0; i < n; i++)
		g[i / sz + 1].arr[g[i / sz + 1].sz++] = x[i];
}
void calc() {
	int idx = 0;
	for (int i = 1; i <= gg; i++) {
		for (int j = 0; j < g[i].sz; j++) 
			t[idx++] = g[i].arr[j];
		g[i].sz = 0;
	}
	gg = (idx + sz - 1) / sz;
	for (int i = 0; i < idx; i++) 
		g[i / sz + 1].arr[g[i / sz + 1].sz++] = t[i];
	for (int i = 1; i <= gg; i++)
		g[i].improve();
}
void erase(int now) {
	int ng;
	for (ng = gg; ng > 1; ng--)
		if (g[ng].arr[0] <= now)break;
	int idx;
	for (idx = 0; idx < g[ng].sz; idx++)
		if (g[ng].arr[idx] == now)break;
	g[ng].sz--;
	for (int i = idx; i < g[ng].sz; i++)
		g[ng].arr[i] = g[ng].arr[i + 1];
	if (!g[ng].sz)calc();
	else g[ng].improve();
}
void insert(int now) {
	int ng;
	for (ng = gg; ng > 1; ng--)
		if (g[ng].arr[0] <= now)break;
	int idx;
	for (idx = 0; idx < g[ng].sz; idx++)
		if (now < g[ng].arr[idx])break;
	for (int i = g[ng].sz; i > idx; i--)
		g[ng].arr[i] = g[ng].arr[i - 1];
	g[ng].sz++;
	g[ng].arr[idx] = now;
	g[ng].improve();
}
int get_ans() {
	int ret = 0;
	int last = -1;
	for (int i = 1; i <= gg; i++) {
		int le, ri, mid, idx;
		le = 0;
		ri = g[i].sz - 1;
		idx = -1;
		while (le <= ri) {
			mid = (le + ri) / 2;
			if (last < g[i].arr[mid]) {
				idx = mid;
				ri = mid - 1;
			}
			else
				le = mid + 1;
		}
		if (idx == -1)continue;
		last = g[i].last[idx];
		ret += g[i].cnt[idx];
	}
	return ret;
}
int update(int i, int y){
	if (cnt%sz == 0)calc();
	erase(x[i]);
	insert(x[i]=y);
	cnt++;
	return get_ans();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 4192 KB Output is correct
2 Correct 357 ms 4432 KB Output is correct
3 Correct 532 ms 5540 KB Output is correct
4 Correct 575 ms 5540 KB Output is correct
5 Correct 604 ms 7004 KB Output is correct
6 Correct 696 ms 8456 KB Output is correct
7 Correct 592 ms 9516 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 9516 KB Output is correct
2 Correct 588 ms 9516 KB Output is correct
3 Correct 1123 ms 9748 KB Output is correct
4 Correct 1250 ms 10260 KB Output is correct
5 Correct 1294 ms 10264 KB Output is correct
6 Correct 1869 ms 10276 KB Output is correct
7 Correct 1249 ms 12468 KB Output is correct
8 Correct 1247 ms 14416 KB Output is correct
9 Correct 949 ms 15900 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3711 ms 18776 KB Output is correct
2 Correct 3903 ms 18776 KB Output is correct
3 Correct 2973 ms 18776 KB Output is correct
4 Correct 4034 ms 18776 KB Output is correct
5 Correct 4172 ms 23772 KB Output is correct
6 Correct 603 ms 23772 KB Output is correct
7 Correct 564 ms 25496 KB Output is correct
8 Correct 617 ms 28320 KB Output is correct
9 Correct 577 ms 31348 KB Output is correct
10 Correct 3921 ms 39824 KB Output is correct
11 Correct 2917 ms 43652 KB Output is correct
12 Correct 3565 ms 48456 KB Output is correct
13 Correct 3359 ms 53372 KB Output is correct
14 Correct 2527 ms 57828 KB Output is correct
15 Correct 3489 ms 62632 KB Output is correct
16 Correct 3618 ms 66312 KB Output is correct
17 Correct 3459 ms 71024 KB Output is correct
18 Correct 3401 ms 74740 KB Output is correct
19 Correct 4352 ms 79196 KB Output is correct
20 Correct 4262 ms 83804 KB Output is correct