Submission #17021

#	Time	Username	Problem	Language	Result	Execution time	Memory
17021		erdemkiraz	Dancing Elephants (IOI11_elephants)	C++98	26 / 100	9000 ms	34856 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 = 150000 + 5;
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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3