Submission #1263185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263185		Aviansh	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	1070 ms	175268 KiB

obstacles

#include <bits/stdc++.h>
using namespace std;

// -------------------- Segment Tree --------------------
struct segTree {
    int *st;
    int n;
    segTree(int siz){
        int x = ceil(log2(siz));
        x++;
        n = siz - 1;
        st = new int[(1<<x)];
        fill(st, st+(1<<x), 0);
    }

    void rupdate(int l, int r, int ind, int i, int val){
        if(i < l || i > r) return;
        if(l == r){
            st[ind] = val;
            return;
        }
        int mid = (l+r)/2;
        rupdate(l, mid, ind*2+1, i, val);
        rupdate(mid+1, r, ind*2+2, i, val);
        st[ind] = min(st[ind*2+1], st[ind*2+2]);
    }

    void update(int i, int val){
        rupdate(0, n, 0, i, val);
    }

    int rquery(int l, int r, int s, int e, int ind){
        if(e < l || s > r) return 1e9;
        if(s <= l && r <= e) return st[ind];
        int mid = (l+r)/2;
        return min(rquery(l, mid, s, e, ind*2+1), rquery(mid+1, r, s, e, ind*2+2));
    }

    int query(int l, int r){
        return rquery(0, n, l, r, 0);
    }

    // return {index, value}
    pair<int,int> rleftmost(int l, int r, int s, int e, int ind, int val){
        if(e < l || s > r) return {1e9,1e9};
        if(st[ind] > val) return {1e9,1e9};
        if(l == r) return {l, st[ind]};
        int mid = (l+r)/2;
        pair<int,int> p = rleftmost(l, mid, s, e, ind*2+1, val);
        if(p.second <= val) return p;   // ✅ fixed
        return rleftmost(mid+1, r, s, e, ind*2+2, val);
    }

    int lefmost(int l, int r, int val){
        return rleftmost(0, n, l, r, 0, val).first;
    }

    pair<int,int> rrigtmost(int l, int r, int s, int e, int ind, int val){
        if(e < l || s > r) return {1e9,1e9};
        if(st[ind] > val) return {1e9,1e9};
        if(l == r) return {l, st[ind]};
        int mid = (l+r)/2;
        pair<int,int> p = rrigtmost(mid+1, r, s, e, ind*2+2, val);
        if(p.second <= val) return p;   // ✅ fixed
        return rrigtmost(l, mid, s, e, ind*2+1, val);
    }

    int rigmost(int l, int r, int val){
        return rrigtmost(0, n, l, r, 0, val).first;
    }
};

// -------------------- Globals --------------------
const int maxm = 2e5+5;
const int lg = 20;

long long conv(array<int,2>a){
    return (((long long)a[0])<<20)|a[1];
}

segTree seg(maxm);

unordered_map<long long,vector<pair<int,array<int,2>>>> g;
unordered_map<long long,vector<pair<int,array<int,2>>>> parl;
unordered_map<long long,vector<pair<int,array<int,2>>>> parr;

vector<array<int,2>> rs;

// -------------------- DFS --------------------
void dfs(pair<int,array<int,2>> node){
    array<int,2> st = node.second;
    int req = 1e9;
    if(g[conv(st)].size()){
        req = g[conv(st)][0].first;
    }
    if(parl.find(conv(st)) != parl.end()){
        return;
    }

    int reql = seg.lefmost(st[0], st[1], req);
    int reqr = seg.rigmost(st[0], st[1], req);

    parl[conv(st)] = vector<pair<int,array<int,2>>>(lg, {-1, st});
    parr[conv(st)] = vector<pair<int,array<int,2>>>(lg, {1e9, st});

    if(g[conv(st)].size() == 0){
        return;
    }

    dfs(g[conv(st)][0]);

    array<int,2> las = g[conv(st)][0].second;

    vector<pair<int,array<int,2>>> temp(lg);
    temp[0] = {reql, g[conv(st)][0].second};

    for(int i=1;i<lg;i++){
        temp[i] = {max(temp[i-1].first, parl[conv(las)][i-1].first), parl[conv(las)][i-1].second};
        las = temp[i].second;
    }
    parl[conv(st)] = temp;

    temp[0] = {reqr, g[conv(st)][0].second};
    las = g[conv(st)][0].second;
    for(int i=1;i<lg;i++){
        temp[i] = {min(temp[i-1].first, parr[conv(las)][i-1].first), parr[conv(las)][i-1].second};
        las = temp[i].second;
    }
    parr[conv(st)] = temp;
}

// -------------------- Initialize --------------------
void initialize(vector<int> T, vector<int> H) {
    int n = T.size();
    int m = H.size();

    vector<array<int,2>> elems;
    for(int i=0;i<m;i++){
        seg.update(i, H[i]);
        elems.push_back({H[i], i});
    }
    sort(elems.begin(), elems.end());

    segTree stt(n);
    for(int i=0;i<n;i++){
        stt.update(i, T[i]);
    }

    // current ranges
    int las = -1;
    for(int i=0;i<m;i++){
        if(T[0] <= H[i]){
            if(las != -1){
                rs.push_back({las, i-1});
            }
            las = -1;
        } else {
            if(las == -1) las = i;
        }
    }
    if(las != -1) rs.push_back({las, m-1});

    // graph building
    set<array<int,2>> rangs;
    map<array<int,2>,int> mp;
    auto it = elems.begin();

    for(int i=0;i<n;i++){
        while(it!=elems.end() && (*it)[0] < T[i]){
            int ind = (*it)[1];
            array<int,2> rang = {ind, ind};
            bool wor = 0;
            int x = 0;
            array<int,2> up = {-1,-1};
            auto itup = rangs.lower_bound(rang);
            if(itup != rangs.end()){
                up = *itup;
                if(up[0] == ind+1){
                    rang[1] = up[1];
                    x = stt.query(mp[up], i);
                    if(x > seg.query(up[0], up[1])){
                        wor = 1;
                    }
                    rangs.erase(up);
                }
            }
            auto itdow = rangs.lower_bound(rang);
            if(itdow != rangs.begin()){
                itdow--;
                array<int,2> dow = *itdow;
                if(dow[1] == ind-1){
                    rang[0] = dow[0];
                    int f = stt.query(mp[dow], i);
                    if(f > seg.query(dow[0], dow[1])){
                        g[conv(dow)].push_back({f, rang});
                    }
                    rangs.erase(dow);
                }
            }
            rangs.insert(rang);
            if(wor){
                g[conv(up)].push_back({x, rang});
            }
            it++;
        }
    }
    for(array<int,2>a: rs){
        dfs({T[0], a});
    }
}

// -------------------- LCA --------------------
array<int,2> lca(array<int,2> a, array<int,2> b){
    if(a == b){
        return {1000000000, -1};
    }
    int l = -1;
    int r = 1e9;

    for(int i=lg-1;i>=0;i--){
        pair<int,array<int,2>> p = parl[conv(a)][i];
        array<int,2> posa = p.second;
        if(posa[0] <= b[0] && b[1] <= posa[1]) continue;
        l = max(l, p.first);
        r = min(r, p.first);
        a = posa;
    }

    for(int i=lg-1;i>=0;i--){
        pair<int,array<int,2>> p = parl[conv(b)][i];
        array<int,2> posb = p.second;
        if(posb[0] <= a[0] && a[1] <= posb[1]) continue;
        l = max(l, p.first);
        r = min(r, p.first);
        b = posb;
    }

    if(a[0] <= b[0] && b[1] <= a[1]){
        l = max(l, parl[conv(b)][0].first);
        r = min(r, parr[conv(b)][0].first);
        b = parl[conv(b)][0].second;
    }
    else if(b[0] <= a[0] && a[1] <= b[1]){
        swap(a, b);
        l = max(l, parl[conv(b)][0].first);
        r = min(r, parr[conv(b)][0].first);
        b = parl[conv(b)][0].second;
    }
    else{
        l = max(l, parl[conv(b)][0].first);
        r = min(r, parr[conv(b)][0].first);
        b = parl[conv(b)][0].second;
        swap(a, b);
        l = max(l, parl[conv(b)][0].first);
        r = min(r, parr[conv(b)][0].first);
        b = parl[conv(b)][0].second;
    }

    return {l, r};   // ✅ fixed
}

// -------------------- can_reach --------------------
bool can_reach(int L, int R, int S, int D) {
    if(S > D) swap(S, D);

    array<int,2> rangs = *(upper_bound(rs.begin(), rs.end(), (array<int,2>){S,1000000000})-1);
    array<int,2> rangd = *(upper_bound(rs.begin(), rs.end(), (array<int,2>){D,1000000000})-1);

    if(parl[conv(rangs)][lg-1].second != parl[conv(rangd)][lg-1].second){
        return 0;
    }

    array<int,2> arr = lca(rangs, rangd);

    if(arr[0] < L || arr[1] > R) return 0;
    return 1;
}

• 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