oj.uz

Submission #43760

# Submission time Handle Problem Language Result Execution time Memory
43760 2018-03-22T18:15:32 Z baactree Dancing Elephants (IOI11_elephants) C++14
26 / 100
 4022 ms 9252 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++) 
		t[i] = x[i] = X[i];
	cnt = 0;
	sz = 390;
	gg = (n + sz - 1) / sz;
}
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;
	}
	for (int i = 0; i < n; 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 2400 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 2472 KB Output is correct
2 Correct 3 ms 2544 KB Output is correct
3 Correct 3 ms 2560 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 3492 KB Output is correct
2 Correct 323 ms 3796 KB Output is correct
3 Correct 445 ms 4820 KB Output is correct
4 Incorrect 33 ms 4928 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 4928 KB Output is correct
2 Correct 531 ms 4928 KB Output is correct
3 Correct 1117 ms 5128 KB Output is correct
4 Correct 1196 ms 5848 KB Output is correct
5 Correct 1292 ms 5848 KB Output is correct
6 Incorrect 45 ms 5848 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3783 ms 9192 KB Output is correct
2 Correct 4022 ms 9252 KB Output is correct
3 Correct 3033 ms 9252 KB Output is correct
4 Incorrect 87 ms 9252 KB Output isn't correct
5 Halted 0 ms 0 KB -