Submission #1257320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257320		jwvg0425	Obstacles for a Llama (IOI25_obstacles)	C++20	24 / 100	1002 ms	95688 KiB

obstacles

#include "obstacles.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;


constexpr int clog2(int n) { return ((n < 2) ? 1 : 1 + clog2(n / 2)); }

class SegmentTree
{
public:
    SegmentTree() = default;

    void init(const vector<int>& raw_)
    {
        raw = raw_;
        n = (int)raw.size();
        int sz = (1 << (clog2(n) + 1));
        data.resize(sz);

        _init(raw, 1, 0, n - 1);
    }

    int update(int idx, const int& newVal) { raw[idx] = newVal; return _update(1, 0, n - 1, idx, newVal); }
    int query(int left, int right) { return _query(1, 0, n - 1, left, right); }

private:
    vector<int> raw;
    vector<int> data;
    int n;

    int merge(int l, int r) { return max(l, r); }

    int _init(const vector<int>& raw, int node, int start, int end)
    {
        int mid = (start + end) / 2;
        if (start == end)
            return data[node] = raw[start];
        else
            return data[node] = merge(_init(raw, node * 2, start, mid),
                _init(raw, node * 2 + 1, mid + 1, end));
    }

    int _update(int node, int start, int end, int index, const int& newVal)
    {
        if (index < start || index > end)
            return data[node];

        if (start == end)
            data[node] = newVal;
        else
        {
            int mid = (start + end) / 2;
            data[node] = merge(_update(node * 2, start, mid, index, newVal),
                _update(node * 2 + 1, mid + 1, end, index, newVal));
        }

        return data[node];
    }

    int _query(int node, int start, int end, int left, int right)
    {
        if (left <= start && end <= right)
            return data[node];

        int mid = (start + end) / 2;

        if (mid < left)
            return _query(node * 2 + 1, mid + 1, end, left, right);

        if (mid + 1 > right)
            return _query(node * 2, start, mid, left, right);

        return merge(_query(node * 2, start, mid, left, right),
            _query(node * 2 + 1, mid + 1, end, left, right));
    }
};

vector<int> t, h;
vector<int> tmin;
vector<int> tmax;
int lbig[200005];
int rbig[200005];
int li[200005];
int ri[200005];
int nxt[200005][20];
int lnxt[200005][20];
int rnxt[200005][20];

int nxtl[200005][20];
int nxtr[200005][20];
SegmentTree canMoveMax;

// 도달 가능 범위가 l..r을 안 벗어나는 범위에서 최대한 확장
int nxtmost(int st, int l, int r)
{
    for (int i = 19; i >= 0; i--)
    {
        if (nxtl[st][i] < l || nxtr[st][i] > r)
            continue;

        st = nxt[st][i];
    }

    if (l <= li[st] && ri[st] <= r)
        st = nxt[st][0];

    return st;
}

int lmost(int st, int l)
{
    for (int i = 19; i >= 0; i--)
    {
        int k = lnxt[st][i];

        if (k < l)
            continue;

        st = k;
    }

    return st;
}

int rmost(int st, int r)
{
    for (int i = 19; i >= 0; i--)
    {
        int k = rnxt[st][i];

        if (k > r)
            continue;

        st = k;
    }

    return st;
}

bool can_reach(int l, int r, int s, int d)
{
    s = nxtmost(s, l, r);

    s = lmost(s, l);
    s = rmost(s, r);

    return li[s] <= d && d <= ri[s];
}

void initialize(vector<int> T, vector<int> H)
{
    t = T;
    h = H;
    tmin = T;
    tmax = T;

    for (int i = 1; i < t.size(); i++)
    {
        tmin[i] = min(tmin[i - 1], t[i]);
        tmax[i] = max(tmax[i - 1], t[i]);
    }

    vector<int> lbs;

    for (int i = 0; i < h.size(); i++)
    {
        while (!lbs.empty() && h[lbs.back()] >= h[i])
            lbs.pop_back();

        if (lbs.empty())
            lbig[i] = -1;
        else
            lbig[i] = lbs.back();

        lbs.push_back(i);
    }

    vector<int> rbs;
    for (int i = h.size() - 1; i >= 0; i--)
    {
        while (!rbs.empty() && h[rbs.back()] >= h[i])
            rbs.pop_back();

        if (rbs.empty())
            rbig[i] = h.size();
        else
            rbig[i] = rbs.back();

        rbs.push_back(i);
    }

    vector<int> canLive(h.size());
    vector<int> canMove(h.size());

    for (int i = 0; i < h.size(); i++)
    {
        canLive[i] = -1;
        int lo = 0, hi = t.size() - 1;

        while (lo <= hi)
        {
            int mid = (lo + hi) / 2;

            if (tmin[mid] > h[i])
            {
                canLive[i] = mid;
                lo = mid + 1;
            }
            else
            {
                hi = mid - 1;
            }
        }

        nxt[i][0] = i;
        lnxt[i][0] = i;
        rnxt[i][0] = i;
    }


    for (int i = 0; i < h.size(); i++)
    {
        canMove[i] = t.size();
        int lo = 0, hi = t.size() - 1;

        while (lo <= hi)
        {
            int mid = (lo + hi) / 2;

            if (tmax[mid] > h[i])
            {
                canMove[i] = mid;
                hi = mid - 1;
            }
            else
            {
                lo = mid + 1;
            }
        }
    }

    canMoveMax.init(canMove);

    for (int i = 0; i < h.size(); i++)
    {
        int sl = i, sr = i;

        int lo = 0, hi = i;
        int target = canLive[i];
        while (lo <= hi)
        {
            int mid = (lo + hi) / 2;
            auto v = canMoveMax.query(mid, i);
            if (v > target)
            {
                lo = mid + 1;
            }
            else
            {
                sl = mid;
                hi = mid - 1;
            }
        }

        lo = i;  hi = h.size() - 1;
        while (lo <= hi)
        {
            int mid = (lo + hi) / 2;
            auto v = canMoveMax.query(i, mid);
            if (v > target)
            {
                hi = mid - 1;
            }
            else
            {
                sr = mid;
                lo = mid + 1;
            }
        }

        li[i] = sl;
        ri[i] = sr;
    }

    for (int i = 0; i < h.size(); i++)
    {
        vector<int> canNxt;

        if (li[i] <= lbig[i])
        {
            canNxt.push_back(lbig[i]);
            lnxt[i][0] = lbig[i];
        }

        if (ri[i] >= rbig[i])
        {
            canNxt.push_back(rbig[i]);
            rnxt[i][0] = rbig[i];
        }

        if (canNxt.size() == 2)
        {
            if (h[canNxt[0]] > h[canNxt[1]])
                nxt[i][0] = canNxt[0];
            else
                nxt[i][0] = canNxt[1];
        }

        if (canNxt.size() == 1)
            nxt[i][0] = canNxt[0];

        nxtl[i][0] = min(i, nxt[i][0]);
        nxtr[i][0] = max(i, nxt[i][0]);
    }

    for (int l = 1; l < 20; l++)
    {
        for (int i = 0; i < h.size(); i++)
        {
            nxt[i][l] = nxt[nxt[i][l - 1]][l - 1];
            nxtl[i][l] = min(nxtl[i][l - 1], nxtl[nxt[i][l - 1]][l - 1]);
            nxtr[i][l] = max(nxtr[i][l - 1], nxtr[nxt[i][l - 1]][l - 1]);
            lnxt[i][l] = lnxt[lnxt[i][l - 1]][l - 1];
            rnxt[i][l] = rnxt[rnxt[i][l - 1]][l - 1];
        }
    }
}

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