Submission #521074

#	Time	Username	Problem	Language	Result	Execution time	Memory
521074		Cyanmond	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9076 ms	6072 KiB

elephants

#line 1 "paper.cpp"
#include <bits/stdc++.h>

#line 3 "library2/utility/len.hpp"

template <class Container> int len(const Container&c){
    return static_cast<int>(std::size(c));
}
#line 5 "library2/utility/lwb.hpp"

template <class Container, class T> constexpr int lwb(const Container &c, const T &val) {
    return static_cast<int>(std::distance(c.cbegin(), std::lower_bound(c.cbegin(), c.cend(), val)));
}
#line 3 "library2/utility/rep.hpp"

class Range {
    struct Iterator {
        int itr;
        constexpr Iterator(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept {
            ++itr;
        }
        constexpr bool operator!=(const Iterator &other) const noexcept {
            return itr != other.itr;
        }
        constexpr int operator*() const noexcept {
            return itr;
        }
    };
    const Iterator first, last;

  public:
    explicit constexpr Range(const int f, const int l) noexcept
        : first(f), last(std::max(f, l)) {}
    constexpr Iterator begin() const noexcept {
        return first;
    }
    constexpr Iterator end() const noexcept {
        return last;
    }
};

constexpr Range rep(const int l, const int r) noexcept {
    return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
    return Range(0, n);
}
#line 3 "library2/utility/revrep.hpp"

class ReversedRange {
    struct Iterator {
        int itr;
        constexpr Iterator(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept {
            --itr;
        }
        constexpr bool operator!=(const Iterator &other) const noexcept {
            return itr != other.itr;
        }
        constexpr int operator*() const noexcept {
            return itr;
        }
    };
    const Iterator first, last;

  public:
    explicit constexpr ReversedRange(const int f, const int l) noexcept
        : first(l - 1), last(std::min(f, l) - 1) {}
    constexpr Iterator begin() const noexcept {
        return first;
    }
    constexpr Iterator end() const noexcept {
        return last;
    }
};

constexpr ReversedRange revrep(const int l, const int r) noexcept {
    return ReversedRange(l, r);
}
constexpr ReversedRange revrep(const int n) noexcept {
    return ReversedRange(0, n);
}
#line 3 "library2/utility/scan.hpp"

template <typename T = int> T scan() {
    T ret;
    std::cin >> ret;
    return ret;
}
#line 5 "library2/utility/upb.hpp"

template <class Container, class T> constexpr int upb(const Container &c, const T &val) {
    return static_cast<int>(std::distance(c.cbegin(), std::upper_bound(c.cbegin(), c.cend(), val)));
}
#line 9 "paper.cpp"

constexpr int NB = 2, QB = 1000;

int N, L;
std::vector<int> X;
int blocks;
int count_query;

struct Warp {
    int last;
    int cost;
};

std::vector<int> limit;
std::vector<std::vector<std::pair<int, int>>> data;
std::vector<std::vector<Warp>> map;

std::vector<Warp> recalc(const std::vector<std::pair<int, int>> &x) {
    const int n = len(x);
    std::vector<Warp> ret(n);
    int to = n;
    for (const int i : revrep(n)) {
        while (x[i].first + L < x[to - 1].first) {
            --to;
        }
        if (to == n) {
            ret[i] = {i, 0};
        } else {
            const auto &to_value = ret[to];
            ret[i] = {to_value.last, to_value.cost + 1};
        }
    }
    return ret;
}

void reset_all() {
    std::vector<std::pair<int, int>> sorted_data;
    auto collect = [&]() {
        for (const int i : rep(blocks)) {
            for (const auto &e : data[i]) {
                sorted_data.push_back(e);
            }
        }
    };

    auto re_allocate = [&]() {
        for (const int i : rep(blocks)) {
            data[i].clear();
            const int l = i * NB, r = std::min(len(sorted_data), (i + 1) * NB);
            if (l >= r) {
                break;
            }
            data[i].reserve(r - l);
            for (const int j : rep(l, r)) {
                data[i].push_back(sorted_data[j]);
            }
            map[i] = recalc(data[i]);
        }
    };

    collect();
    re_allocate();

    auto calc_limit = [&]() {
        for (const int i : rep(blocks)) {
            if (data[i].empty()) {
                limit[i] = std::numeric_limits<int>::max() - 10;
            } else {
                limit[i] = data[i][0].first;
            }
        }
        limit[0] = 0;
    };

    calc_limit();
}

void erase(const int value) {
    const int block = upb(limit, value) - 1;
    const auto itr =
        std::lower_bound(data[block].begin(), data[block].end(), std::make_pair(value, 1));
    if (itr->first == value) {
        --data[block][itr - data[block].begin()].second;
        if (data[block][itr - data[block].begin()].second == 0) {
            data[block].erase(itr);
        }
    }
    map[block] = recalc(data[block]);
}

void insert(const int value) {
    const int block = upb(limit, value) - 1;
    const auto itr =
        std::lower_bound(data[block].begin(), data[block].end(), std::make_pair(value, 1));
    if (itr->first == value) {
        ++data[block][itr - data[block].begin()].second;
    } else {
        data[block].insert(itr, {value, 1});
    }
    map[block] = recalc(data[block]);
}

void init(int n, int l, int x[]) {
    N = n;
    L = l;
    count_query = 0;
    std::copy(x, x + N, std::back_inserter(X));
    blocks = (n + NB - 1) / NB;
    limit.resize(blocks);
    data.resize(blocks);
    map.resize(blocks);
    for (const int i : rep(N)) {
        if (i == 0 or X[i] != X[i - 1]) {
            data[0].push_back({X[i], 1});
        } else {
            ++data[0].back().second;
        }
    }
    reset_all();
}

int calc_answer() {
    int ret = 0, now_block = -1, last = 0;

    auto find_next = [&](const int value) {
        while (true) {
            ++now_block;
            if (now_block == blocks) {
                break;
            }
            if (data[now_block].empty()) {
                continue;
            }
            if (data[now_block].back().first < last) {
                continue;
            }
            break;
        }
        if (now_block == blocks) {
            return -1;
        }
        return lwb(data[now_block], std::make_pair(value, 1));
    };

    while (true) {
        const int idx = find_next(last);
        if (idx == -1) {
            break;
        }
        ret += map[now_block][idx].cost;
        ++ret;
        last = data[now_block][map[now_block][idx].last].first + L + 1;
        if (now_block == blocks - 1) {
            break;
        }
    }

    return ret;
}

int update(int i, int y) {
    ++count_query;
    if (count_query % QB == 0) {
        reset_all();
    }
    erase(X[i]);
    insert(y);
    X[i] = y;
    return calc_answer();
}

/*
int main() {
    int n, l, m;
    std::cin >> n >> l >> m;
    int x[100];
    for (const int i : rep(n)) {
        std::cin >> x[i];
    }
    init(n, l, x);
    while (m--) {
        int i, y;
        std::cin >> i >> y;
        std::cout << update(i, y) << std::endl;
    }
}
*/

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