Submission #1305961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305961		alosza	Obstacles for a Llama (IOI25_obstacles)	C++20	37 / 100	147 ms	15156 KiB

obstacles

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define FORD(i, l, r) for(int i = (l); i >= (r); i--)

struct min_tree
{
    vector<int> tr;
    int n;
    
    min_tree() {}
    min_tree(int _n) : n(_n)
    {
        tr.resize(2 * n);
    }
    
    void insert(int i, int v)
    {
        for(tr[i += n] = v; i > 1; i >>= 1) tr[i>>1] = min(tr[i], tr[i^1]);
    }
    
    int get(int l, int r)
    {
        r++;
        int res = INT_MAX;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1)
        {
            if(l&1) res = min(res, tr[l++]);
            if(r&1) res = min(res, tr[--r]);
        }
        return res;
    }
};

struct max_tree
{
    vector<int> tr;
    int n;
    
    max_tree() {}
    max_tree(int _n) : n(_n)
    {
        tr.resize(2 * n);
    }
    
    void insert(int i, int v)
    {
        for(tr[i += n] = v; i > 1; i >>= 1) tr[i>>1] = max(tr[i], tr[i^1]);
    }
    
    int get(int l, int r)
    {
        r++;
        int res = 0;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1)
        {
            if(l&1) res = max(res, tr[l++]);
            if(r&1) res = max(res, tr[--r]);
        }
        return res;
    }
};
vector<int> lt, rt;
min_tree mint, mint_temp;
max_tree maxt;
int n, m;
vector<pair<int, int>> cands; //candidates for first one > x

void initialize(vector<int> T, vector<int> H)
{
    n = T.size();
    m = H.size();
    
    mint = min_tree(m);
    maxt = max_tree(m);
    FOR(i, 0, m) mint.insert(i, H[i]), maxt.insert(i, H[i]);
    mint_temp = min_tree(n);
    FOR(i, 0, n) mint_temp.insert(i, T[i]);


    int t0 = T[0];
    lt.resize(m);
    {
        int left = -1;
        FOR(i, 0, m)
        {
            if(t0 <= H[i]) left = i;
            else lt[i] = left + 1;
        }
    }

    rt.resize(m);
    {
        int right = m;
        FORD(i, m - 1, 0)
        {
            if(t0 <= H[i]) right = i;
            else rt[i] = right - 1;
        }
    }

    cands.emplace_back(T[0], 0);
    FOR(i, 0, n)
    {
        if(T[i] > cands.back().first) cands.emplace_back(T[i], i);
    }
}

bool can_reach(int L, int R, int _S, int _D)
{
    int S = min(_S, _D), D = max(_S, _D);
    int ls = max(lt[S], L), rs = min(rt[S], R);
    int ld = max(lt[D], L), rd = min(rt[D], R);

    int minH = max(mint.get(ls, rs), mint.get(ld, rd));
    int maxH = maxt.get(S, D);
    
    int path = -1;
    {
        auto it = upper_bound(cands.begin(), cands.end(), make_pair(maxH, INT_MAX));
        if(it == cands.end()) return false;
        path = it->second;
    }

    if(mint_temp.get(0, path - 1) <= minH) return false;
    return true;
}

• 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