Submission #1255722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255722		EJIC_B_KEDAX	Obstacles for a Llama (IOI25_obstacles)	C++20	37 / 100	1270 ms	129032 KiB

obstacles

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

using namespace std;

struct rmq {
    vector<pair<int, int>> st;
    size_t sz;
    rmq() = default;
    rmq(vector<int> a) {
        sz = 1;
        while (sz < a.size()) {
            sz <<= 1;
        }

        st.resize(2 * sz, make_pair(0, -1));
        for (int i = 0; i < a.size(); i++) {
            st[i + sz] = {a[i], i};
        }
        for (int i = sz - 1; i > 0; i--) {
            st[i] = min(st[2 * i], st[2 * i + 1]);
        }
    }
    pair<int, int> get(int l, int r) {
        l += sz; r += sz;
        pair<int, int> res = {INT32_MAX, -1};
        while (l <= r) {
            if (l & 1) {
                res = min(res, st[l++]);
            }
            if (~r & 1) {
                res = min(res, st[r--]);
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

vector<int> ord;

struct forest {
    vector<int> d;
    vector<vector<int>> binup, binupx, binupn;
    int timer;
    void add_vertice(int idx, int p) {
        // cout << "! " << idx << ' ' << p << '\n';
        ord[idx] = timer;
        if (p == -1) {
            d[idx] = 0;
            for (int l = 0; l < binup.size(); l++) {
                binup[l][idx] = idx;
                binupx[l][idx] = idx;
                binupn[l][idx] = idx;
            }
            return;
        }
        d[idx] = d[p] + 1;
        binup[0][idx] = p;
        binupx[0][idx] = max(p, idx);
        binupn[0][idx] = min(p, idx);
        for (int l = 1; l < binup.size(); l++) {
            binup[l][idx] = binup[l - 1][binup[l - 1][idx]];
            binupx[l][idx] = max(binupx[l - 1][binup[l - 1][idx]], binupx[l - 1][idx]);
            binupn[l][idx] = min(binupn[l - 1][binup[l - 1][idx]], binupn[l - 1][idx]);
        }
    }
    int up(int idx, int l1, int r1) {
        int res = idx;
        for (int l = binup.size() - 1; l >= 0; l--) {
            if (binupn[l][res] >= l1 && binupx[l][res] <= r1) {
                res = binup[l][res];
            }
        }
        return res;
    }
    pair<int, int> up(int idx, int amount) {
        pair<int, int> res = {idx, idx};
        for (int l = binup.size() - 1; l >= 0; l--) {
            if (amount & (1 << l)) {
                res.second = max(res.second, binupx[l][res.first]);
                res.first = binup[l][res.first];
            }
        }
        return res;
    }
    forest() = default;
    forest(vector<int> t, vector<int> h) {
        d.resize(h.size());
        ord.resize(h.size());
        timer = 0;
        binup.resize(20);
        binupx.resize(20);
        binupn.resize(20);
        for (int i = 0; i < binup.size(); i++) {
            binup[i].resize(h.size());
            binupx[i].resize(h.size());
            binupn[i].resize(h.size());
        }
        int cur = t.size();
        int now = 0;
        rmq tmin(t), tmax;
        {
            vector<int> tmp = t;
            for (int i = 0; i < tmp.size(); i++) {
                tmp[i] *= -1;
            }
            tmax = rmq(tmp);
        }
        vector<pair<int, int>> sh;
        for (int i = 0; i < h.size(); i++) {
            sh.emplace_back(h[i], i);
        }
        ranges::sort(sh);
        int ptr = 0, ptr2 = sh.size() - 1;
        set<int> closed, open;
        while (cur > 0) {
            // cout << "! " << cur << endl;
            int next = -1;
            if (!now) {
                next = tmax.get(0, cur - 1).second;
                int val = t[next];
                while (ptr2 >= 0 && sh[ptr2].first >= val) {
                    closed.insert(sh[ptr2--].second);
                }
            }
            if (now || next == 0) {
                if (next == -1) {
                    next = tmin.get(0, cur - 1).second;
                }
                vector<int> nw;
                int val = t[next];
                while (ptr < sh.size() && sh[ptr].first < val) {
                    nw.push_back(sh[ptr++].second);
                }
                ranges::sort(nw);

                for (int i : nw) {
                    auto sptr = open.lower_bound(i);
                    bool ok = true;
                    if (sptr == open.begin()) {
                        ok = false;
                    } else {
                        sptr--;
                        int free = *sptr;
                        auto sptr2 = closed.lower_bound(free);
                        if (sptr2 != closed.end() && *sptr2 <= i) {
                            ok = false;
                        }
                    }
                    if (ok) {
                        add_vertice(i, *sptr);
                    } else {
                        sptr = open.lower_bound(i);
                        ok = true;
                        if (sptr == open.end()) {
                            ok = false;
                        } else {
                            int free = *sptr;
                            auto sptr2 = closed.lower_bound(i);
                            if (sptr2 != closed.end() && *sptr2 <= free) {
                                ok = false;
                            }
                        }
                        if (ok) {
                            add_vertice(i, *sptr);
                        } else {
                            add_vertice(i, -1);
                        }
                    }
                    open.insert(i);
                }
            }

            now = 1 - now;
            cur = next;
            timer++;
        }
        for (int i = 0; i < h.size(); i++) {
            if (open.find(i) == open.end()) {
                add_vertice(i, -1);
            }
        }
    }
};

forest l_forest, r_forest;
rmq hmin;
int n;

void initialize(vector<int> t, vector<int> h) {
    l_forest = forest(t, h);
    hmin = rmq(h);
    ranges::reverse(h);
    r_forest = forest(t, h);
    n = h.size();
}

bool can_reach(int L, int R, int S, int D) {
    if (S > D) swap(S, D);
    int m = hmin.get(S, D).second;
    int ds = r_forest.d[n - 1 - S];
    int dd = l_forest.d[D];
    int dmr = r_forest.d[n - 1 - m];
    int dml = l_forest.d[m];
    auto [rv, rb] = r_forest.up(n - 1 - S, ds - dmr);
    auto [lv, lb] = l_forest.up(D, dd - dml);
    if (rv == n - 1 - m && lv == m && lb <= R && rb <= n - 1 - L) return true;
    int lll = l_forest.up(D, L, R);
    int rrr = r_forest.up(n - 1 - S, n - 1 - R, n - 1 - L);
    if (n - 1 - rrr >= D && lll <= S) return true;
    return false;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17