Submission #1254527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254527		TadijaSebez	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	273 ms	82140 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=200050;
const int LOG=20;
int rmq[N][LOG];
int par[N][LOG];
int rpar[N][LOG];
int lpar[N][LOG];
int anc[N];
pair<int,int> rng[N];
int myMx[N];

const int inf=1e9+7;

const int M=2*N;
int ls[M],rs[M],tsz,root;
pair<int,int> mn[M];
void Build(int&c,int ss,int se,vector<int>&H){
    c=++tsz;
    if(ss==se){
        mn[c]={H[ss],ss};
        return;
    }
    int mid=ss+se>>1;
    Build(ls[c],ss,mid,H);
    Build(rs[c],mid+1,se,H);
    mn[c]=min(mn[ls[c]],mn[rs[c]]);
}
pair<int,int> Get(int c,int ss,int se,int qs,int qe){
    if(qs>qe||qs>se||ss>qe)return {inf,-1};
    if(qs<=ss&&qe>=se)return mn[c];
    int mid=ss+se>>1;
    return min(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe));
}

void BuildRMQ(vector<int> H){
    int n=H.size();
    for(int i=0;i<n;i++){
        rmq[i][0]=H[i];
    }
    for(int j=1;j<LOG;j++){
        for(int i=0;i<n-(1<<j)+1;i++){
            rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
        }
    }
    Build(root,0,n-1,H);
}
int Get(int l,int r){
    int k=31-__builtin_clz(r-l+1);
    return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
}

pair<int,int> GetRange(int n,int i,int mn){
    int top=n-1,bot=i,R=i;
    while(top>=bot){
        int mid=top+bot>>1;
        if(Get(i,mid)<mn){
            R=mid;
            bot=mid+1;
        }else{
            top=mid-1;
        }
    }
    top=i,bot=0;
    int L=i;
    while(top>=bot){
        int mid=top+bot>>1;
        if(Get(mid,i)<mn){
            L=mid;
            top=mid-1;
        }else{
            bot=mid+1;
        }
    }
    return {L,R};
}

void initialize(vector<int> T, vector<int> H) {
    int n=T.size();
    int m=H.size();
    vector<pair<int,int>> rngs;
    for(int i=0;i<n;i++){
        if(rngs.empty()){
            rngs.pb({T[i],T[i]});
        }else{
            rngs.pb({min(rngs.back().first,T[i]),max(rngs.back().second,T[i])});
        }
    }
    BuildRMQ(H);
    vector<int> ord;
    for(int i=0;i<m;i++){
        ord.pb(i);
        int top=(int)rngs.size()-1,bot=0,best=-1;
        while(top>=bot){
            int mid=top+bot>>1;
            if(rngs[mid].first>H[i]){
                best=mid;
                bot=mid+1;
            }else{
                top=mid-1;
            }
        }
        if(best!=-1){
            myMx[i]=rngs[best].second;
            pair<int,int> seg=GetRange(m,i,rngs[best].second);
            //printf("range(%i) = %i %i\n",i,seg.first,seg.second);
            lpar[i][0]=Get(root,0,m-1,seg.first,i).second;
            par[i][0]=Get(root,0,m-1,seg.first,seg.second).second;
            rpar[i][0]=Get(root,0,m-1,i,seg.second).second;
            rng[i]=seg;
        }else{
            rng[i]={i,i};
            myMx[i]=-1;
            par[i][0]=i;
            lpar[i][0]=i;
            rpar[i][0]=i;
        }
        anc[i]=par[i][0];
        //printf("%i: myMx:%i par:%i lpar:%i rpar:%i rng:(%i, %i)\n",i,myMx[i],par[i][0],lpar[i][0],rpar[i][0],rng[i].first,rng[i].second);
    }
    sort(ord.begin(),ord.end(),[&](int i,int j){return H[i]<H[j];});
    for(int i:ord){
        anc[i]=anc[anc[i]];
        for(int j=1;j<LOG;j++){
            lpar[i][j]=lpar[lpar[i][j-1]][j-1];
            par[i][j]=par[par[i][j-1]][j-1];
            rpar[i][j]=rpar[rpar[i][j-1]][j-1];
        }
        //printf("%i: root:%i\n",i,par[i][0]);
    }
}

bool Inside(int L,int R,pair<int,int> a){
    return L<=a.first && R>=a.second;
}

int Lift(int u,int L,int R){
    return anc[u];
    for(int i=LOG-1;i>=0;i--){
        if(Inside(L,R,rng[par[u][i]])){
            u=par[u][i];
        }
    }
    if(Inside(L,R,{par[u][0],par[u][0]})){
        u=par[u][0];
    }
    int l=u,r=u;
    for(int i=LOG-1;i>=0;i--){
        //printf("%i ",lpar[l][i]);
        if(lpar[l][i]>=L){
            l=lpar[l][i];
        }
        if(rpar[r][i]<=R){
            r=rpar[r][i];
        }
    }
    //printf("l:%i r:%i\n",l,r);
    return myMx[l]<myMx[r]?r:l;
}

bool can_reach(int L, int R, int S, int D) {
    //printf("L:%i R:%i S:%i D:%i\n",L,R,S,D);
    S=Lift(S,L,R);
    D=Lift(D,L,R);
    //printf("Lift(S):%i Lift(D):%i\n",S,D);
    int mx=min(myMx[S],myMx[D]);
    return Get(min(S,D),max(S,D))<mx;
}

• 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