제출 #99620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99620		naoai	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	6885 ms	12164 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

static const int nmax = 15e4;
static const int rad = 400 * 4;

static int n, L;
static int up_cnt;
static int bucket[nmax + 1];
static pair<int, int> pozitii[nmax + 1];

static int nrb;
static int sz[nmax / rad + 1];

struct str {
    int x, ind, pos, dp;
};

str v[nmax / rad + 1][2 * rad + 5];

void compute (int b) {
    int ind = sz[b];
    for (int i = sz[b] - 1; i >= 0; -- i) {
        while (ind - 1 > i && v[b][ind - 1].x > v[b][i].x + L) {
            -- ind;
        }

        if (ind == sz[b]) {
            v[b][i].dp = 1;
            v[b][i].pos = v[b][i].x + L;
        } else {
            v[b][i].dp = v[b][ind].dp + 1;
            v[b][i].pos = v[b][ind].pos;
        }
    }
}

void refa_bucketuri () {
    int idx = 0;
    for (int b = 0; b < nrb; ++ b) {
        for (int k = 0; k < sz[b]; ++ k) {
            pozitii[idx ++] = {v[b][k].x, v[b][k].ind};
        }

        sz[b] = 0;
    }

    for (int i = 0, b = 0; i < n; i += rad, ++ b) {
        for (int j = i; j < i + rad && j < n; ++ j) {
            v[b][sz[b]].x = pozitii[j].first;
            v[b][sz[b] ++].ind = pozitii[j].second;
            bucket[pozitii[j].second] = b;
        }

        compute(b);
    }
}

void init (int N, int l, int X[]) {
    n = N;
    L = l;

    for (int i = 0; i < n; i += rad, ++ nrb) {
        for (int j = i; j < i + rad && j < n; ++ j) {
            v[nrb][sz[nrb]].x = X[j];
            v[nrb][sz[nrb] ++].ind = j;
        }
    }

    refa_bucketuri();
}

int solve () {
    int total = 0;
    int posst = -1;

    int n2 = 1;
    for (n2 = 1; (n2 << 1) <= 3 * rad; n2 <<= 1) {
    }

    for (int i = 0; i < nrb; ++ i) {
        if (sz[i] == 0) continue;
        if (v[i][sz[i] - 1].x <= posst)
            continue;

        int pos = -1;
        for (int step = n2; step > 0; step >>= 1) {
            if (pos + step < sz[i] && v[i][pos + step].x <= posst)
                pos += step;
        }

        ++ pos;
        total += v[i][pos].dp;
        posst = v[i][pos].pos;
    }

    return total;
}

int update(int I, int y) {
    ++ up_cnt;

    if (up_cnt % rad == 0) {
        refa_bucketuri();
    }

    // sterg i
    int ind = bucket[I], pos = -1;
    for (int i = 0; i < sz[ind]; ++ i)
        if (v[ind][i].ind == I)
            pos = i;

    for (int i = pos; i < sz[ind] - 1; ++ i)
        v[ind][i] = v[ind][i + 1];
    -- sz[ind];
    compute(ind);

    //caut bucket nou
    ind = 0;
    while (ind + 1 < nrb && v[ind + 1][0].x <= y)
        ++ ind;
    pos = 0;
    while (pos < sz[ind] && v[ind][pos].x <= y)
        ++ pos;

    // inserez in ind, pos
    for (int i = sz[ind] - 1; i >= pos; -- i)
        v[ind][i + 1] = v[ind][i];

    v[ind][pos].x = y;
    v[ind][pos].ind = I;

    bucket[I] = ind;
    ++ sz[ind];
    compute(ind);

    return solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3