Submission #1261210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261210		Faggi	Obstacles for a Llama (IOI25_obstacles)	C++20	10 / 100	2097 ms	30520 KiB

obstacles

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
vector<ll>t,h, seg, I, D;
vector<pair<ll,ll>>seg2;
ll n, m, pot=1;
void initialize(std::vector<int> T, std::vector<int> H) {
    for(auto k:T)
        t.pb(k);
    for(auto k:H)
        h.pb(k);
    while(pot<sz(h))
        pot*=2;
    seg.resize(pot*2,0);
    seg2.resize(pot*2,{LLONG_MAX,-1});
    I.resize(pot*2);
    D.resize(pot*2);
    ll i;
    for(i=pot; i<pot*2; i++)
        I[i]=D[i]=i;
    for(i=0; i<sz(H); i++)
    {
        seg[i+pot]=H[i];
        seg2[i+pot]={H[i],i};
    }
    for(i=pot-1; i>0; i--)
    {
        I[i]=I[i*2];
        D[i]=D[i*2+1];
        seg[i]=max(seg[i*2],seg[i*2+1]);
        seg2[i]=seg2[i*2];
        if(seg2[i*2+1].fr<seg2[i].fr)
            seg2[i]=seg2[i*2+1];
    }
  return;
}

ll calc(ll a, ll b, ll nod)
{
    if(I[nod]>b||D[nod]<a)
        return 0;
    if(I[nod]>=a&&D[nod]<=b)
        return seg[nod];
    return max(calc(a,b,nod*2),calc(a,b,nod*2+1));
}

pair<ll,ll> calc2(ll a, ll b, ll nod)
{
    if(I[nod]>b||D[nod]<a)
        return {LLONG_MAX,-1};
    if(I[nod]>=a&&D[nod]<=b)
        return seg2[nod];
    pair<ll,ll>r1,r2;
    r1=calc2(a,b,nod*2);
    r2=calc2(a,b,nod*2+1);
    if(r1.fr>r2.fr)
        return r2;
    return r1;
}

bool con(ll i, ll ja, ll jb)
{
    ll ma=0, j;
    ma=calc(ja+pot,jb+pot,1);
    if(ma>=t[i])
        return 0;
    return 1;
}

ll minR(ll i, ll j)
{
    ll mi=LLONG_MAX, pj=-1, l=0, r=j, piv, ma, pos=-1;
    while(l<=r)
    {
        piv=(l+r)/2;
        ma=calc(piv+pot,j+pot,1);
        if(ma>=t[i])
        {
            l=piv+1;
        }
        else
        {
            r=piv-1;
            pos=piv;
        }
    }
    pair<ll,ll>ret;
    if(pos!=-1)
    {
        ret=calc2(pos+pot,j+pot,1);
        if(mi>ret.fr)
        {
            mi=ret.fr;
            pj=ret.se;
        }
    }
    pos=-1;
    l=j;r=m-1;
    while(l<=r)
    {
        piv=(l+r)/2;
        ma=calc(piv+pot,j+pot,1);
        if(ma>=t[i])
        {
            l=piv+1;
        }
        else
        {
            r=piv-1;
            pos=piv;
        }
    }
    if(pos!=-1)
    {
        ret=calc2(j+pot,pos+pot,1);
        if(mi>ret.fr)
        {
            mi=ret.fr;
            pj=ret.se;
        }
    }
    return pj;
}

bool can_reach(int L, int R, int S, int D) {
    n=sz(t); m=sz(h);
    ll i;
    if(S>D)
        swap(S,D);
    for(i=0; i<n; i++)
    {
        if(con(i,S,D))
            return 1;
        if(i+1<n)
        {
            S=minR(i,S);
            D=minR(i,D);
            if(S==-1||D==-1)
                return 0;
        }
    }
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17