oj.uz

답안 #521074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521074 2022-01-31T17:12:43 Z Cyanmond 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
26 / 100
 9000 ms 6072 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 = 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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 3016 ms 2172 KB Output is correct
8 Correct 4222 ms 2620 KB Output is correct
9 Correct 6641 ms 5440 KB Output is correct
10 Correct 4492 ms 5508 KB Output is correct
11 Correct 4389 ms 5512 KB Output is correct
12 Execution timed out 9076 ms 6072 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 3016 ms 2172 KB Output is correct
8 Correct 4222 ms 2620 KB Output is correct
9 Correct 6641 ms 5440 KB Output is correct
10 Correct 4492 ms 5508 KB Output is correct
11 Correct 4389 ms 5512 KB Output is correct
12 Execution timed out 9076 ms 6072 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 3016 ms 2172 KB Output is correct
8 Correct 4222 ms 2620 KB Output is correct
9 Correct 6641 ms 5440 KB Output is correct
10 Correct 4492 ms 5508 KB Output is correct
11 Correct 4389 ms 5512 KB Output is correct
12 Execution timed out 9076 ms 6072 KB Time limit exceeded
13 Halted 0 ms 0 KB -