Submission #1274817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274817		mehrzad	Obstacles for a Llama (IOI25_obstacles)	C++20	37 / 100	218 ms	73540 KiB

obstacles

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

using ll = long long;
const ll NEG = -4e18;               // sentinel for impossible B

/*---------------------------------------------------------------*/
/*  segment tree for (max B , index)                             */
struct SegMaxB {
    int n;
    vector<pair<ll,int>> t;         // (B , index)
    SegMaxB(int _n=0){init(_n);}
    void init(int _n){
        n=1; while(n<_n) n<<=1;
        t.assign(2*n, {NEG,-1});
    }
    // set position p (0‑based)
    void setVal(int p, ll B, int idx){
        p+=n;
        t[p] = {B, idx};
        for(p>>=1; p; p>>=1){
            t[p] = (t[p<<1].first >= t[p<<1|1].first) ? t[p<<1] : t[p<<1|1];
        }
    }
    // query max on [l,r] inclusive
    pair<ll,int> query(int l,int r){
        if(l>r) return {NEG,-1};
        l+=n; r+=n;
        pair<ll,int> ans = {NEG,-1};
        while(l<=r){
            if(l&1){
                if(t[l].first > ans.first) ans = t[l];
                ++l;
            }
            if(!(r&1)){
                if(t[r].first > ans.first) ans = t[r];
                --r;
            }
            l>>=1; r>>=1;
        }
        return ans;
    }
};

/*---------------------------------------------------------------*/
/*  segment tree for range maximum of H                           */
struct SegMaxH {
    int n;
    vector<int> t;
    SegMaxH(int _n=0){init(_n);}
    void init(int _n){
        n=1; while(n<_n) n<<=1;
        t.assign(2*n, INT_MIN);
    }
    void setVal(int p, int val){
        p+=n;
        t[p]=val;
        for(p>>=1; p; p>>=1) t[p]=max(t[p<<1], t[p<<1|1]);
    }
    int query(int l,int r){               // inclusive
        if(l>r) return INT_MIN;
        l+=n; r+=n;
        int ans = INT_MIN;
        while(l<=r){
            if(l&1) ans = max(ans, t[l++]);
            if(!(r&1)) ans = max(ans, t[r--]);
            l>>=1; r>>=1;
        }
        return ans;
    }
};

/*---------------------------------------------------------------*/
/*  sparse table for range minimum/maximum (integer)               */
struct SparseTable {
    int N, K;
    vector<vector<int>> st;
    vector<int> lg;
    bool isMin;            // true -> min, false -> max
    SparseTable(){}
    SparseTable(const vector<int> &a, bool _isMin){
        build(a,_isMin);
    }
    void build(const vector<int> &a, bool _isMin){
        isMin = _isMin;
        N = (int)a.size();
        K = 1;
        while((1<<K) <= N) ++K;
        lg.assign(N+1,0);
        for(int i=2;i<=N;i++) lg[i]=lg[i/2]+1;
        st.assign(K, vector<int>(N));
        st[0]=a;
        for(int k=1;k<K;k++){
            for(int i=0;i+(1<<k)<=N;i++){
                if(isMin)
                    st[k][i]=min(st[k-1][i], st[k-1][i+(1<<(k-1))]);
                else
                    st[k][i]=max(st[k-1][i], st[k-1][i+(1<<(k-1))]);
            }
        }
    }
    // query on [l,r] inclusive
    int query(int l,int r) const{
        if(l>r) return isMin?INT_MAX:INT_MIN;
        int k = lg[r-l+1];
        if(isMin)
            return min(st[k][l], st[k][r-(1<<k)+1]);
        else
            return max(st[k][l], st[k][r-(1<<k)+1]);
    }
};

/*---------------------------------------------------------------*/
/*  global data                                                   */
static vector<int> T, H;
static vector<int> prefMin, prefMax;
static vector<int> deepest;          // -1 … N-1
static vector<ll> B;                 // -inf for useless columns
static vector<int> blockId;          // -1 for non‑free0
static vector<int> blockLeft, blockRight;   // per block
static SegMaxB segB;
static SegMaxH segH;
static SparseTable stLeftGood, stRightGood; // leftGood min , rightGood max
static vector<int> leftGood, rightGood;      // size M-1

/*---------------------------------------------------------------*/
void initialize(vector<int> TT, vector<int> HH){
    T.swap(TT);  H.swap(HH);
    int N = T.size();
    int M = H.size();

    /* prefix minima / maxima of T */
    prefMin.resize(N);
    prefMax.resize(N);
    for(int i=0;i<N;i++){
        prefMin[i] = (i==0? T[i] : min(prefMin[i-1], T[i]));
        prefMax[i] = (i==0? T[i] : max(prefMax[i-1], T[i]));
    }

    /* deepest and B for every column */
    deepest.assign(M, -1);
    B.assign(M, NEG);
    for(int j=0;j<M;j++){
        // first index where prefMin <= H[j]
        int lo=0, hi=N-1, pos=N;
        while(lo<=hi){
            int mid=(lo+hi)/2;
            if(prefMin[mid] <= H[j]){
                pos=mid;
                hi=mid-1;
            }else lo=mid+1;
        }
        if(pos==0) deepest[j] = -1;
        else if(pos==N) deepest[j] = N-1;
        else deepest[j] = pos-1;
        if(deepest[j] >= 0) B[j] = prefMax[deepest[j]];
    }

    /* free0 columns and block decomposition */
    blockId.assign(M, -1);
    vector<int> blockOfCol;      // only for free columns
    blockLeft.clear(); blockRight.clear();
    int curBlk = -1;
    for(int j=0;j<M;j++){
        if(H[j] < T[0]){
            if(curBlk==-1){
                curBlk = (int)blockLeft.size();
                blockLeft.push_back(j);
                blockRight.push_back(j);
                blockOfCol.push_back(curBlk);
            }else{
                blockRight[curBlk]=j;
                blockOfCol.push_back(curBlk);
            }
            blockId[j]=curBlk;
        }else{
            curBlk=-1;
            blockOfCol.push_back(-1);
        }
    }

    /* segment tree for max B (only for free0 columns) */
    segB.init(M);
    for(int j=0;j<M;j++){
        if(B[j]!=NEG) segB.setVal(j, B[j], j);
    }

    /* segment tree for max H */
    segH.init(M);
    for(int j=0;j<M;j++) segH.setVal(j, H[j]);

    /* ----- compute leftGood and rightGood ---------------------- */
    // first next index with H >= B
    vector<int> nextGe(M, M);
    for(int j=0;j<M;j++){
        if(B[j]==NEG){ nextGe[j]=j+1; continue; }
        int lo=j+1, hi=M-1, pos=M;
        while(lo<=hi){
            int mid=(lo+hi)/2;
            if(H[mid] >= B[j]){
                pos=mid; hi=mid-1;
            }else lo=mid+1;
        }
        nextGe[j]=pos;
    }
    // rightLimit from (3)
    vector<int> rightLimit(M, -2);   // -2 means cannot cross any border
    for(int j=0;j<M;j++){
        if(B[j]==NEG) continue;
        rightLimit[j] = nextGe[j]-2;            // may become -1, -2 etc.
    }

    // sweep left to right, maintain active columns (rightLimit >= cur)
    leftGood.assign(max(0,M-1), -1);
    vector<vector<int>> deactivate(M); // at border x we deactivate cols with rightLimit == x-1
    for(int j=0;j<M;j++){
        if(rightLimit[j]>=j){
            int stop = rightLimit[j]+1;                 // first border where it stops
            if(stop < M) deactivate[stop].push_back(j);
        }
    }
    // segment tree for max index among active columns
    struct SegIdx {
        int n; vector<int> t;
        SegIdx(int _n=0){init(_n);}
        void init(int _n){
            n=1; while(n<_n) n<<=1;
            t.assign(2*n, -1);
        }
        void setVal(int p, int v){
            p+=n; t[p]=v;
            for(p>>=1;p;p>>=1) t[p]=max(t[p<<1], t[p<<1|1]);
        }
        int query(int l,int r){
            if(l>r) return -1;
            l+=n; r+=n;
            int ans=-1;
            while(l<=r){
                if(l&1) ans=max(ans,t[l++]);
                if(!(r&1)) ans=max(ans,t[r--]);
                l>>=1; r>>=1;
            }
            return ans;
        }
    } segIdx;
    segIdx.init(M);
    // initially none active
    for(int border=0; border<M-1; ++border){
        // activate column border (it becomes usable exactly at its own border)
        if(rightLimit[border]>=border){
            segIdx.setVal(border, border);
        }
        // deactivate columns that stop before next border
        for(int col: deactivate[border+1]){
            segIdx.setVal(col, -1);
        }
        leftGood[border] = segIdx.query(0, border);
    }

    // now rightGood (mirror)
    vector<int> prevGe(M, -1);
    for(int j=0;j<M;j++){
        if(B[j]==NEG){ prevGe[j]=j-1; continue; }
        int lo=0, hi=j-1, pos=-1;
        while(lo<=hi){
            int mid=(lo+hi)/2;
            if(H[mid] >= B[j]){
                pos=mid; lo=mid+1;
            }else hi=mid-1;
        }
        prevGe[j]=pos;
    }
    vector<int> leftLimit(M, -2);
    for(int j=0;j<M;j++){
        if(B[j]==NEG) continue;
        leftLimit[j] = prevGe[j]+1;   // first border that can be crossed from right side
    }
    // sweep right to left, maintain active columns (leftLimit <= cur)
    rightGood.assign(max(0,M-1), M);
    vector<vector<int>> activate(M); // at border x we activate columns with leftLimit == x
    for(int j=0;j<M;j++){
        if(leftLimit[j]<=j-1){
            int start = leftLimit[j];
            if(start>=0) activate[start].push_back(j);
        }
    }
    // segment tree for minimal index among active columns
    struct SegMinIdx {
        int n; vector<int> t;
        SegMinIdx(int _n=0){init(_n);}
        void init(int _n){
            n=1; while(n<_n) n<<=1;
            t.assign(2*n, INT_MAX);
        }
        void setVal(int p, int v){
            p+=n; t[p]=v;
            for(p>>=1;p;p>>=1) t[p]=min(t[p<<1], t[p<<1|1]);
        }
        int query(int l,int r){
            if(l>r) return INT_MAX;
            l+=n; r+=n;
            int ans=INT_MAX;
            while(l<=r){
                if(l&1) ans=min(ans,t[l++]);
                if(!(r&1)) ans=min(ans,t[r--]);
                l>>=1; r>>=1;
            }
            return ans;
        }
    } segMinIdx;
    segMinIdx.init(M);
    // initially none active
    for(int border=M-2; border>=0; --border){
        // activate columns that become usable at this border
        for(int col: activate[border]){
            segMinIdx.setVal(col, col);
        }
        // columns that are to the left of this border are not usable any more,
        // but we never deactivate because once leftLimit <= border it stays true.
        int cur = segMinIdx.query(border+1, M-1);
        if(cur==INT_MAX) cur = M;   // meaning not existing
        rightGood[border] = cur;
    }

    // build sparse tables for leftGood (min) and rightGood (max)
    if(M>=2){
        stLeftGood = SparseTable(leftGood, true);   // min
        stRightGood = SparseTable(rightGood, false); // max
    }
}

/*---------------------------------------------------------------*/
bool can_reach(int L, int R, int S, int D){
    if(S==D) return true;
    int blkS = blockId[S];
    int blkD = blockId[D];
    if(blkS==-1 || blkD==-1) return false; // should not happen

    if(blkS == blkD) return true; // same row‑0 block

    // intersection of destination block with the interval
    int dL = max(L, blockLeft[blkD]);
    int dR = min(R, blockRight[blkD]);
    if(dL > dR) return false;          // destination block not inside interval

    // intersection of start block with the interval
    int sL = max(L, blockLeft[blkS]);
    int sR = min(R, blockRight[blkS]);
    if(sL > sR) return false;

    // best (max B) column inside start block part
    auto bestStart = segB.query(sL, sR);
    ll BmaxStart = bestStart.first;
    int p = bestStart.second;           // column index of that best start column

    // best (max B) column inside destination block part
    auto bestDest = segB.query(dL, dR);
    ll BmaxDest = bestDest.first;

    // threshold V
    ll V = min(BmaxStart, BmaxDest);
    if(V==NEG) return false;           // should not happen

    // column q of destination block that is closest to p
    int q;
    if(S < D) q = dL;      // leftmost column of dest block
    else      q = dR;      // rightmost column of dest block

    int lo = min(p,q), hi = max(p,q);
    int maxH = segH.query(lo, hi);

    return ( (ll)maxH < V );
}

• 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