Submission #1251821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251821		Zbyszek99	Obstacles for a Llama (IOI25_obstacles)	C++20	100 / 100	523 ms	216312 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9;

struct table
{
    pii min_[200001][18];
    pii max_[200001][18];
    void set(vi v)
    {
        rep(i,siz(v))
        {
            min_[i][0] = {v[i],i};
            max_[i][0] = {v[i],i};
        }
        rep2(bit,1,17)
        {
            rep(i,siz(v))
            {
                min_[i][bit] = min(min_[i][bit-1],(i+(1<<(bit-1)) < siz(v) ? min_[i+(1<<(bit-1))][bit-1] : (pii){1e9,1e9}));
                max_[i][bit] = max(max_[i][bit-1],(i+(1<<(bit-1)) < siz(v) ? max_[i+(1<<(bit-1))][bit-1] : (pii){-1e9,-1e9}));
            }
        }
    }
    pii get_max(int l, int r)
    {
        int lg = __lg(r-l+1);
        return max(max_[l][lg],max_[r-(1 << lg)+1][lg]);
    }
    pii get_min(int l, int r)
    {
        int lg = __lg(r-l+1);
        return min(min_[l][lg],min_[r-(1 << lg)+1][lg]);
    }
};

struct jump_str
{
    int l,r,v;
    jump_str operator+(const jump_str& other)
    {
        jump_str res;
        res.l = min(l,other.l);
        res.r = max(r,other.r);
        res.v = other.v;
        return res;
    }
};

table tableX;
table tableY;
jump_str jump[500001][18];
int vert[200001];
int X[200001];
int Y[200001];
vi pref;
int cur_v = 0;
int vH[500001];

void split(int l, int r, int h, vector<pii>& ans)
{
    if(l > r) return;
    int max_col = tableX.get_max(l,r).ss;
    if(Y[h] > X[max_col]) ans.pb({l,r});
    else
    {
        split(l,max_col-1,h,ans);
        split(max_col+1,r,h,ans);
    }
}

jump_str get_jump(int l, int r, int h, int prev)
{
    jump_str j = {(int)1e9,(int)-1e9,prev};
    int pop_H = vH[prev];
    int l2 = l;
    int r2 = r;
    while(l2 <= r2)
    {
        int mid = (l2+r2)/2;
        if(tableX.get_min(mid,r).ff < tableY.get_min(h,pop_H).ff)
        {
            j.l = mid;
            l2 = mid+1;
        }
        else
        {
            r2 = mid-1;
        }
    }
    l2 = l;
    r2 = r;
    while(l2 <= r2)
    {
        int mid = (l2+r2)/2;
        if(tableX.get_min(l,mid).ff < tableY.get_min(h,pop_H).ff)
        {
            j.r = mid;
            r2 = mid-1;
        }
        else
        {
            l2 = mid+1;
        }
    }
    return j;
}

void rek(int l, int r, int pref_max, int pop)
{
    int v = cur_v++;
    vH[v] = pref[pref_max];
    
    if(pop != -1) jump[v][0] = get_jump(l,r,pref[pref_max],pop);
    else jump[v][0] = {(int)1e9,(int)-1e9,v};

    int max_col = tableX.get_max(l,r).ss;
    int l2 = 0;
    int r2 = pref_max;
    int down_ok = pref_max;
    while(l2 <= r2)
    {
        int mid = (l2+r2)/2;
        if(Y[pref[mid]] > X[max_col])
        {
            down_ok = mid;
            r2 = mid-1;
        }
        else
        {
            l2 = mid+1;
        }
    }
    vector<pii> segs;
    if(down_ok != 0) split(l,r,pref[down_ok-1],segs);
    else segs.pb({l,r});

    int v_down = cur_v++;
    vH[v_down] = pref[down_ok];

    if(down_ok != pref_max)
    {   
        if(tableY.get_min(pref[down_ok],pref[pref_max]).ff <= tableX.get_min(l,r).ff)
        {
            jump[v_down][0] = {(int)1e9,(int)-1e9,v_down};
        }
        else
        {
            jump[v_down][0] = get_jump(l,r,pref[down_ok],v);
        }
    }
    else
    {
        jump[v_down][0] = {(int)1e9,(int)-1e9,v};
    }
    if(down_ok == 0)
    {
        rep2(i,l,r)
        {
            vert[i] = v_down;
        }
        return;
    }
    forall(it,segs)
    {
        if(tableY.get_min(pref[down_ok-1],pref[down_ok]).ff > tableX.get_min(it.ff,it.ss).ff)
        {
            rek(it.ff,it.ss,down_ok-1,v_down);
        }
        else
        {
            rek(it.ff,it.ss,down_ok-1,-1);
        }
    }
}

void initialize(vi T, vi H) 
{
    rep(i,siz(T)) Y[i] = T[i];
    rep(i,siz(H)) X[i] = H[i];
    tableY.set(T);
    tableX.set(H);
    int pop = -1;
    rep(i,siz(T))
    {
        if(Y[i] >= pop)
        {
            pref.pb(i);
            pop = Y[i];
        }
    }
    vH[0] = pref.back();
    rek(0,siz(H)-1,siz(pref)-1,-1);
    rep2(bit,1,17)
    {
        rep(i,cur_v)
        {
            jump[i][bit] = jump[i][bit-1] + jump[jump[i][bit-1].v][bit-1];
        }
    }
}

bool can_reach(int L, int R, int S, int D) 
{
    if(S > D) swap(D,S);
    int v1 = vert[S];
    int v2 = vert[D];
    for(int bit = 17; bit >= 0; bit--)
    {
        if(jump[v1][bit].l >= L)
        {
            v1 = jump[v1][bit].v;
        }
        if(jump[v2][bit].r <= R)
        {
            v2 = jump[v2][bit].v;
        }
    }
    int row = min(vH[v1],vH[v2]);
    return tableX.get_max(S,D).ff < Y[row];
}

• 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: 17 / 17