oj.uz

Submission #17028

# Submission time Handle Problem Language Result Execution time Memory
17028 2015-11-04T12:43:46 Z erdemkiraz Dancing Elephants (IOI11_elephants) C++
10 / 100
 9000 ms 38668 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 150000 + 5;
const int K = 2;
const int T = N / K + 5;

int n, l;
int a[N], gr[N], nxt[N], need[N], group[T];
set < ii > s[T], all;

void rebuild(int i) {
	group[i] = -1;
	int last = 0;
	if(s[i].size())
		last = (--s[i].end()) -> first;
	for(set < ii > :: reverse_iterator it = s[i].rbegin(); it != s[i].rend(); it++) {
		int x = it -> first;
		int id = it -> second;
		gr[id] = i;
		int next = all.lower_bound(ii(x + l + 1, 0)) -> second;
		//printf("id = %d next = %d\n", id, next);
		if(a[next] <= last) {
			need[id] = need[next] + 1;
			nxt[id] = nxt[next];
		}
		else {
			need[id] = 1;
			nxt[id] = next;
		}
	}
}

ii b[N];

void init() {
	all.clear();
	for(int i = 0; i < n; i++) {
		all.insert(ii(a[i], i));
		b[i] = ii(a[i], i);
	}
	a[n] = 2 * inf;
	all.insert(ii(2 * inf, n));
	sort(b, b + n);
	for(int i = 0; i * K < n; i++) {
		s[i].clear();
		for(int j = i * K; j < n and j < (i + 1) * K; j++) {
			s[i].insert(b[j]);
		}
		rebuild(i);
	}
}

void init(int N, int L, int X[]) {
	n = N;
	l = L;
	for(int i = 0; i < n; i++) {
		a[i] = X[i];
	}
	init();
}

int update(int i, int x) {
	int ind = -1;
	for(int j = 0; j * K < n; j++) {
		if(s[j].count(ii(a[i], i))) {
			ind = j;
			break;
		}
	}
	assert(ind != -1);
	s[ind].erase(ii(a[i], i));
	all.erase(ii(a[i], i));
	int aft = all.lower_bound(ii(a[i] + 1, 0)) -> second;
	for(int j = ind - 1; j >= 0; j--) {
		if(s[j].size()) {
			int st = s[j].begin() -> second;
			if(a[st] + l >= a[aft]) {
				group[j] = i;
			}
			else {
				rebuild(j);
				break;
			}
		}
	}
	rebuild(ind);
	a[i] = x;
	for(int j = 0; j * K < n; j++) {
		ind = j;
		if(s[j].size() and x <= (--s[j].end()) -> first)
			break;
	}
	all.insert(ii(a[i], i));
	s[ind].insert(ii(a[i], i));
	rebuild(ind);
	for(int j = ind - 1; j >= 0; j--) {
		if(s[j].size()) {
			int st = s[j].begin() -> second;
			if(a[st] + l >= a[i]) {
				group[j] = i;
			}
			else {
				rebuild(j);
				break;
			}
		}
	}
	int pos = all.begin() -> second, ans = 0;
	while(pos < n) {
		if(group[gr[pos]] != -1) {
			ans++;
			pos = group[gr[pos]];
		}
		else {
			ans += need[pos];
			pos = nxt[pos];
		}
	}
	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24676 KB Output is correct
2 Correct 0 ms 24676 KB Output is correct
3 Correct 4 ms 24676 KB Output is correct

Subtask #2
0.0 / 16.0

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

Subtask #3
0.0 / 24.0

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

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9000 ms 26256 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.0

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