oj.uz

Submission #17011

# Submission time Handle Problem Language Result Execution time Memory
17011 2015-11-04T11:07:15 Z erdemkiraz Dancing Elephants (IOI11_elephants) C++
26 / 100
 9000 ms 20884 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 = 387;
const int T = N / K + 5;

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

void rebuild(int i) {
	int last = 0;
	if(s[i].size())
		last = (--s[i].end()) -> second;
	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 = lower_bound(a, a + n, ii(x + l + 1, 0)) - a;
		//printf("id = %d next = %d\n", id, next);
		if(next <= last) {
			need[id] = need[a[next].second] + 1;
			nxt[id] = nxt[a[next].second];
		}
		else {
			need[id] = 1;
			nxt[id] = next;
		}
	}
}

void init() {
	sort(a, a + n);
	for(int i = 0; i < n; i++)
		w[a[i].second] = i;
	for(int i = 0; i * K < n; i += K) {
		s[i].clear();
		for(int j = i; j < n and j < i + K; j++) {
			s[i].insert(a[j]);
		}
		rebuild(i);
	}
}

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

int update(int i, int x) {
	a[w[i]].first = x;
	init();
	//for(int i = 0; i < n; i++)
	//	printf("%d ", a[i].first);
	//puts("");
	int pos = 0, ans = 0;
	while(pos < n) {
		//printf("pos = %d\n", pos);
		ans += need[a[pos].second];
		pos = nxt[a[pos].second];
	}
	return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0.0 / 24.0

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

Subtask #4
0.0 / 47.0

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

Subtask #5
0.0 / 3.0

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