Submission #1277383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277383		Muhammad_Aneeq	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	356 ms	53120 KiB

obstacles

#include "obstacles.h"
#include "bits/stdc++.h"
using namespace std;
int const MAXN=2e5+10,LG=19;
int rec[MAXN]={};
bool dead[MAXN]={},done[MAXN]={};
int par[MAXN]={};
int mn[MAXN]={};
vector<int>ch[MAXN]={};
struct spr
{
    int tbl[MAXN][LG]={};
    void build(vector<int>a)
    {
        int n=a.size();
        for (int i=0;i<n;i++)
            tbl[i][0]=a[i];
        for (int i=1;(1<<i)<=n;i++)
            for (int j=0;j+(1<<i)-1<n;j++)
                tbl[j][i]=max(tbl[j][i-1],tbl[j+(1<<(i-1))][i-1]);
    }  
    int get(int l,int r)
    {
        int lg=log2(r-l+1);
        return max(tbl[l][lg],tbl[r+1-(1<<lg)][lg]);
    }
};
int root(int n)
{
    return (par[n]==n?n:par[n]=root(par[n]));
}
set<pair<int,int>>S;
void merge(int u,int v)
{
    u=root(u);
    v=root(v);
    if (u==v)
        return;
    ch[u].push_back(v);
    S.erase({mn[u],u});
    S.erase({mn[v],v});
    par[v]=u;
    mn[u]=min(mn[u],mn[v]);
    S.insert({mn[u],u});
}
vector<int>t,h;
spr mh,mt;
void rem(int u,int k)
{
    vector<int>f;
    f.push_back(u);
    for (int i=0;i<f.size();i++)
    {
        for (auto j:ch[f[i]])
        {
            if (!done[j])
                f.push_back(j);
        }
    }
    for (auto i:f)
    {
        done[i]=1;
        rec[i]=min(rec[i],k);
    }
}
void initialize(vector<int> T, vector<int> H) 
{
    t=T;
    h=H;
    int n=t.size(),m=h.size();
    mh.build(h);
    mt.build(t);
    vector<pair<int,int>>vls;
    for (int i=0;i<m;i++)
    {
        rec[i]=n-1,dead[i]=1;
        vls.push_back({h[i],i});
        par[i]=i;
        mn[i]=h[i];
        ch[i]={};
    }
    sort(begin(vls),end(vls));
    reverse(begin(vls),end(vls));
    for (int i=0;i<n;i++)
    {
        while (vls.size()&&t[i]>vls.back().first)
        {
            int ind=vls.back().second;
            vls.pop_back();
            dead[ind]=0;
            S.insert({mn[ind],ind});
            if (ind+1<m&&!dead[ind+1])
                merge(ind,ind+1);
            if (ind-1>=0&&!dead[ind-1])
                merge(ind,ind-1);
        }
        while (S.size()&&(*rbegin(S)).first>=t[i])
        {
            int z=(*rbegin(S)).second;
            rem(z,i-1);
            S.erase(*rbegin(S));
        }
    }
    // cerr<<1<<endl;
    return;
}

bool can_reach(int L, int R, int S, int D)// 105636 85190
{
    if (D<S)
        swap(D,S);
    int z=mh.get(S,D);
    int h=min(rec[S],rec[D]);
    int g=mt.get(0,h);
    // if (D==105636&&S==85190)
    // {
    //     cout<<rec[S]<<' '<<rec[D]<<endl;
    //     cout<<z<<' '<<h<<' '<<g<<endl;
    // }
    if (g>z)
        return 1;
    return false;
}

• 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