제출 #602529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
602529		KoD	식물 비교 (IOI20_plants)	C++17	100 / 100	764 ms	44748 KiB

plants

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

using std::array;
using std::pair;
using std::vector;

template <class F>
struct fixed : private F {
    explicit fixed(F&& f) : F(std::forward<F>(f)) {} 
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

constexpr int INF = std::numeric_limits<int>::max() / 2;
constexpr int LOG = 18;

class lazysegtree {
    int size, logn;
    vector<pair<int, int>> data;
    vector<int> lazy;

    void apply(const int k, const int e) {
        data[k].first += e;
        if (k < size) {
            lazy[k] += e;
        }
    }
    void flush(const int k) {
        if (lazy[k] != 0) {
            apply(2 * k, lazy[k]);
            apply(2 * k + 1, lazy[k]);
            lazy[k] = 0;
        }
    }
    void push(const int k) {
        const int lsb = __builtin_ctz(k);
        for (int d = logn; d > lsb; --d) {
            flush(k >> d);
        }
    }

    void fetch(const int k) {
        data[k] = std::min(data[2 * k], data[2 * k + 1]);
    }
    void pull(int k) {
        k >>= __builtin_ctz(k);
        while (k > 1) {
            fetch(k >>= 1);
        }
    }

  public:
    explicit lazysegtree(const vector<int>& vec) {
        logn = 0;
        while ((1 << logn) < (int)vec.size()) {
            logn += 1;
        }
        size = 1 << logn;
        data.resize(2 * size, {INF, INF});
        for (int i = 0; i < (int)vec.size(); ++i) {
            data[size + i] = {vec[i], i};
        }
        for (int i = size - 1; i > 0; --i) {
            fetch(i);
        }
        lazy.resize(size);
    }

    void disable(int k) {
        k += size;
        for (int d = logn; d > 0; --d) {
            flush(k >> d);
        }
        data[k] = {INF, INF};
        while (k > 1) {
            fetch(k >>= 1);
        }
    }

    void subtract(int l, int r) {
        l += size;
        r += size;
        push(l);
        push(r);
        const int lc = l, rc = r;
        while (l < r) {
            if (l & 1) apply(l++, -1);
            if (r & 1) apply(--r, -1);
            l >>= 1;
            r >>= 1;
        }
        pull(lc);
        pull(rc);
    }

    pair<int, int> fold(int l, int r) {
        l += size;
        r += size;
        push(l);
        push(r);
        pair<int, int> ret = {INF, INF};
        while (l < r) {
            if (l & 1) ret = std::min(ret, data[l++]);
            if (r & 1) ret = std::min(ret, data[--r]);
            l >>= 1;
            r >>= 1;
        }
        return ret;
    }

    pair<int, int> fold() const {
        return data[1];
    }
};

class rangemin {
    int size;
    vector<int> data;

  public:
    explicit rangemin(const int n) : size(n), data(2 * n, INF) {}

    void chmin(int i, const int x) {
        i += size;
        while (i > 0) {
            data[i] = std::min(data[i], x);
            i >>= 1;
        }
    }

    int fold(int l, int r) const {
        l += size;
        r += size;
        int ret = INF;
        while (l < r) {
            if (l & 1) ret = std::min(ret, data[l++]);
            if (r & 1) ret = std::min(ret, data[--r]);
            l >>= 1;
            r >>= 1;
        }
        return ret;
    }
};

int N;
vector<int> order, rank;
array<vector<int>, 18> left, right;

int dist(const int i, const int j) {
    return i <= j ? j - i : j - i + N;
}

int move_left(const int i, const int x) {
    return i >= x ? i - x : i - x + N;
}

int move_right(const int i, const int x) {
    return i + x < N ? i + x : i + x - N;
}

void init(int K, vector<int> R) {
    N = (int)R.size();
    lazysegtree seg(R);
    order.reserve(N);
    while ((int)order.size() < N) {
        fixed([&](auto&& dfs, const int i) -> void {
            while (true) {
                int x, j;
                if (i >= K - 1) {
                    std::tie(x, j) = seg.fold(i - (K - 1), i);
                } else {
                    std::tie(x, j) = std::min(seg.fold(i - (K - 1) + N, N), seg.fold(0, i));
                }
                if (x == 0) {
                    dfs(j);
                } else {
                    break;
                }
            }
            if (i >= K - 1) {
                seg.subtract(i - (K - 1), i);
            } else {
                seg.subtract(i - (K - 1) + N, N);
                seg.subtract(0, i);
            }
            seg.disable(i);
            order.push_back(i);
        })(seg.fold().second);
    }
    rangemin min(N); 
    rank.resize(N);
    left[0].resize(N);
    right[0].resize(N);
    for (int k = N - 1; k >= 0; --k) {
        const int i = order[k];
        rank[i] = k;
        min.chmin(i, k); 
        {
            int x;
            if (i >= K - 1) {
                x = min.fold(i - (K - 1), i);
            } else {
                x = std::min(min.fold(i - (K - 1) + N, N), min.fold(0, i));
            }
            left[0][i] = x == INF ? 0 : dist(order[x], i);
        }
        {
            int x;
            if (i + K <= N) {
                x = min.fold(i + 1, i + K);
            } else {
                x = std::min(min.fold(0, i + K - N), min.fold(i + 1, N));
            }
            right[0][i] = x == INF ? 0 : dist(i, order[x]);
        }
    }
    for (int k = 0; k + 1 < LOG; ++k) {
        left[k + 1].resize(N);
        right[k + 1].resize(N);
        for (int i = 0; i < N; ++i) {
            left[k + 1][i] = std::min(N - 1, left[k][move_left(i, left[k][i])] + left[k][i]);
            right[k + 1][i] = std::min(N - 1, right[k][move_right(i, right[k][i])] + right[k][i]);
        }
    }
}

bool between(const int x, const int l, const int r) {
    if (l <= r) {
        return l <= x and x <= r;
    } else {
        return x <= r or l <= x;
    }
}

int compare_plants(int x, int y) {
    if (rank[x] > rank[y]) {
        return -compare_plants(y, x);
    }
    int a = x, b = x;
    for (int k = LOG - 1; k >= 0; --k) {
        if (const int t = (a - left[k][a] % N + N) % N; !between(y, t, a)) {
            a = t;
        }
        if (const int t = (b + right[k][b]) % N; !between(y, b, t)) {
            b = t;
        }
    }
    if (between(y, move_left(a, left[0][a]), a) and rank[a] < rank[y]) {
        return 1;
    }
    if (between(y, b, move_right(b, right[0][b])) and rank[b] < rank[y]) {
        return 1;
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25