oj.uz

Submission #43758

# Submission time Handle Problem Language Result Execution time Memory
43758 2018-03-22T17:58:55 Z baactree Dancing Elephants (IOI11_elephants) C++14
0 / 100
 3783 ms 25736 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
int n, l;
struct group {
	int sz;
	int arr[1000],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])k--;
				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 = sqrt(n)+1;
	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 = g[ng].sz; idx >= 0; 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;
	ng = max(1, ng);
	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 5200 KB Output is correct
2 Correct 375 ms 6428 KB Output is correct
3 Correct 531 ms 9140 KB Output is correct
4 Incorrect 31 ms 10564 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 11132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3783 ms 20612 KB Output is correct
2 Incorrect 1662 ms 25736 KB Output isn't correct
3 Halted 0 ms 0 KB -