Submission #17011

#	Time	Username	Problem	Language	Result	Execution time	Memory
17011		erdemkiraz	코끼리 (Dancing Elephants) (IOI11_elephants)	C++98	26 / 100	9000 ms	20884 KiB

elephants

#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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3