oj.uz

Submission #521094

# Submission time Handle Problem Language Result Execution time Memory
521094 2022-01-31T17:47:05 Z Cyanmond Dancing Elephants (IOI11_elephants) C++17
97 / 100
 1848 ms 10508 KB 
#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 = 1000, 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) {
                continue;
            }
            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));
    assert(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.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 288 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 618 ms 1940 KB Output is correct
8 Correct 607 ms 2264 KB Output is correct
9 Correct 432 ms 3752 KB Output is correct
10 Correct 423 ms 3744 KB Output is correct
11 Correct 382 ms 3724 KB Output is correct
12 Correct 822 ms 4088 KB Output is correct
13 Correct 410 ms 3840 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 618 ms 1940 KB Output is correct
8 Correct 607 ms 2264 KB Output is correct
9 Correct 432 ms 3752 KB Output is correct
10 Correct 423 ms 3744 KB Output is correct
11 Correct 382 ms 3724 KB Output is correct
12 Correct 822 ms 4088 KB Output is correct
13 Correct 410 ms 3840 KB Output is correct
14 Correct 583 ms 2500 KB Output is correct
15 Correct 886 ms 2744 KB Output is correct
16 Correct 1434 ms 4312 KB Output is correct
17 Correct 1266 ms 5876 KB Output is correct
18 Correct 1389 ms 5768 KB Output is correct
19 Correct 699 ms 5256 KB Output is correct
20 Correct 1313 ms 5856 KB Output is correct
21 Correct 1256 ms 5836 KB Output is correct
22 Correct 594 ms 5280 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 618 ms 1940 KB Output is correct
8 Correct 607 ms 2264 KB Output is correct
9 Correct 432 ms 3752 KB Output is correct
10 Correct 423 ms 3744 KB Output is correct
11 Correct 382 ms 3724 KB Output is correct
12 Correct 822 ms 4088 KB Output is correct
13 Correct 410 ms 3840 KB Output is correct
14 Correct 583 ms 2500 KB Output is correct
15 Correct 886 ms 2744 KB Output is correct
16 Correct 1434 ms 4312 KB Output is correct
17 Correct 1266 ms 5876 KB Output is correct
18 Correct 1389 ms 5768 KB Output is correct
19 Correct 699 ms 5256 KB Output is correct
20 Correct 1313 ms 5856 KB Output is correct
21 Correct 1256 ms 5836 KB Output is correct
22 Correct 594 ms 5280 KB Output is correct
23 Incorrect 1848 ms 10508 KB Output isn't correct
24 Halted 0 ms 0 KB -