Submission #1263162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263162		Aviansh	Obstacles for a Llama (IOI25_obstacles)	C++20	24 / 100	2103 ms	199296 KiB

obstacles

#include <bits/stdc++.h>

using namespace std;

//min segTree

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,val

    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(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;
        }
        return rleftmost(mid+1,r,s,e,ind*2+2,val);
    }

    int lefmost(int l, int r, int val){
        //find leftmost index ie l-ans where query<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(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;
        }
        return rrigtmost(l,mid,s,e,ind*2+1,val);
    }

    int rigmost(int l, int r, int val){
        //find leftmost index ie l-ans where query<val
        return rrigtmost(0,n,l,r,0,val).first;
    }

};

const int maxm = 2e5+5;

segTree seg(maxm);

map<array<int,2>,vector<pair<int,array<int,2>>>>g;

map<array<int,2>,vector<pair<int,array<int,2>>>>parl;
map<array<int,2>,vector<pair<int,array<int,2>>>>parr;

vector<array<int,2>>rs;

const int lg = 20;

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

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

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

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

    dfs(g[st][0]);


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

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

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

    parr[st]=temp;

    if(g[st].size()==0)
        return;
    assert(g[st].size()==1);
    return;
}

void initialize(vector<int> T, vector<int> H) {
    int n = T.size();
    int m = H.size();
    set<array<int,2>>elems;
    for(int i = 0;i<m;i++) {
        seg.update(i,H[i]);
        elems.insert({H[i],i});
    }
    segTree stt(n);
    for(int i = 0;i<n;i++){
        stt.update(i,T[i]);
    }
    //current ranges
    set<array<int,2>>rangs;
    int las = -1;
    for(int i = 0;i<m;i++){
        if(T[0]<=H[i]){
            //bad
            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 between ranges
    //stores when the range was first found
    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()){
                //check if reachable, if yes then nice
                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);
                }
            }
            rangs.insert(rang);
            auto itdow = rangs.lower_bound(rang);
            if(itdow != rangs.begin()){
                itdow--;
                array<int,2>dow = *itdow;
                rangs.erase(rang);
                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[dow].push_back({f,rang});
                    }
                    rangs.erase(dow);
                }
                rangs.insert(rang);
            }
            if(wor){
                g[up].push_back({x,rang});
            }
            it++;
        }
    }
    for(array<int,2>a:rs){
        dfs({T[0],a});
    }
}

array<int,2> lca(array<int,2>a, array<int,2>b){
    if(a==b){
        return {1000000000,-1};
    }
    //must find lca
    int l = -1;
    int r = 1e9;
    //assume lca exists
    for(int i = lg-1;i>=0;i--){
        array<int,2>posa = parl[a][i].second;
        if(posa[0]<=b[0]&&b[1]<=posa[1]){
            //posa is ancestor of b
            continue;
        }
        l=max(l,parl[a][i].first);
        r=min(r,parr[a][i].first);
        a=posa;
    }

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

    if((a[0]<=b[0]&&b[1]<=a[1])){
        //a is anc of b
        l=min(l,parl[b][0].first);
        r=min(r,parr[b][0].first);
        b=parl[b][0].second;
    }
    else if(b[0]<=a[0]&&a[1]<=b[1]){
        swap(a,b);
        l=min(l,parl[b][0].first);
        r=min(r,parr[b][0].first);
        b=parl[b][0].second;
    }
    else{
        //both must be parented
        l=min(l,parl[b][0].first);
        r=min(r,parr[b][0].first);
        b=parl[b][0].second;
        swap(a,b);
        l=min(l,parl[b][0].first);
        r=min(r,parr[b][0].first);
        b=parl[b][0].second;
    }
    assert(a==b);
    return {r,l};
}

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[rangs][19].second!=parl[rangd][19].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: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17