Submission #1255676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255676		EJIC_B_KEDAX	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	793 ms	97516 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<pair<int, int>>> binup;
    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, idx};
            }
            return;
        }
        d[idx] = d[p] + 1;
        binup[0][idx] = {p, max(idx, p)};
        for (int l = 1; l < binup.size(); l++) {
            binup[l][idx] = {binup[l - 1][binup[l - 1][idx].first].first, max(binup[l - 1][binup[l - 1][idx].first].second, binup[l - 1][idx].second)};
        }
    }
    pair<int, int> up(int idx, int l1, int r1) {
        pair<int, int> res = {idx, idx};
        for (int l = binup.size() - 1; l >= 0; l--) {
            if (binup[l][res.first].first >= l1 && max(res.second, binup[l][res.first].second) <= r1) {
                res.second = max(res.second, binup[l][res.first].second);
                res.first = binup[l][res.first].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);
        for (int i = 0; i < binup.size(); i++) {
            binup[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 hmin1, hmin2;
int n;

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

bool can_reach(int L, int R, int S, int D) {
    if (S > D) swap(S, D);
    int ds = r_forest.d[n - 1 - S];
    int dd = l_forest.d[D];
    auto [rv, rb] = r_forest.up(n - 1 - S, n - 1 - R, n - 1 - L);
    auto [lv, lb] = l_forest.up(D, L, R);
    if (lv > n - 1 - rv || ord[lv] != ord[n - 1 - rv]) return false;
    return true;
}

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