제출 #1254313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254313		jwvg0425	장애물 (IOI25_obstacles)	C++20	24 / 100	1835 ms	23588 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;
SegmentTree mtmax;
vector<int> ot, mt; // ot = 잠기는 시점, mt = 이동 가능하게 되는 첫 시점

int par[200005];
int pot[200005];
vector<int> hsort[200005];

int find(int x)
{
    if (x == par[x])
        return x;

    return par[x] = find(par[x]);
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);

    par[x] = y;
    pot[y] = max(pot[y], pot[x]);
}

bool can_reach(int l, int r, int s, int d)
{
    int target = min(ot[s] - 1, ot[d] - 1);

    int sl = s, sr = s;
    int dl = d, dr = d;

    int lo = 0, hi = s;
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        auto v = mtmax.query(mid, s);
        if (v > target)
        {
            lo = mid + 1;
        }
        else
        {
            sl = mid;
            hi = mid - 1;
        }
    }
    lo = 0; hi = d;
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        auto v = mtmax.query(mid, d);
        if (v > target)
        {
            lo = mid + 1;
        }
        else
        {
            dl = mid;
            hi = mid - 1;
        }
    }

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

    int lv = max(sl, dl);
    int rv = min(sr, dr);

    return lv <= rv;
}

void expand(int& l, int& r, int& minh, int v)
{
    while (l > 0 && h[l - 1] < v)
    {
        l--;
        minh = min(minh, h[l]);
    }

    while (r + 1 < h.size() && h[r + 1] < v)
    {
        r++;
        minh = min(minh, h[r]);
    }
}

bool can_reach_n(int s, int d)
{
    int sl = s, sr = s;
    int mins = h[s];
    int dl = d, dr = d;
    int mind = h[d];

    for (int y = 0; y < t.size(); y++)
    {
        // 잠기면 끝
        if (mins >= t[y] || mind >= t[y])
            return false;

        // 아니면 가능한 한 확장
        expand(sl, sr, mins, t[y]);
        expand(dl, dr, mind, t[y]);

        // 확장한 구간이 겹치면 끝
        int l = max(sl, dl);
        int r = min(sr, dr);

        if (l <= r)
            return true;
    }

    return false;
}

void init(vector<int> T, vector<int> H)
{
    t = T;
    tmin = T;
    tmax = T;
    for (int i = 1; i < T.size(); i++)
        tmin[i] = min(tmin[i - 1], t[i]);
    tmin.push_back(-1);

    for (int i = 1; i < T.size(); i++)
        tmax[i] = max(tmax[i - 1], t[i]);
    tmax.push_back(1987654321);

    h = H;

    ot.resize(h.size());
    mt.resize(h.size());

    for (int i = 0; i < h.size(); i++)
    {
        int lo = 0, hi = t.size();

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

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

        hsort[ot[i]].push_back(i);
    }

    for (int i = 0; i < h.size(); i++)
    {
        int lo = 0, hi = t.size();

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

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

    for (int i = 0; i < h.size(); i++)
    {
        par[i] = i;
        pot[i] = ot[i];
    }

    for (int i = h.size(); i >= 0; i--)
    {
        for (auto& hi : hsort[i])
        {

            if (hi > 0 && pot[find(hi)] > mt[hi - 1] && h[hi-1] > i)
                merge(hi, hi - 1);

            if (hi + 1 < h.size() && pot[find(hi)] > mt[hi + 1] && h[hi+1] > i)
                merge(hi, hi + 1);
        }
    }

    for (int i = 0; i < h.size(); i++)
        ot[i] = pot[find(i)];

    mtmax.init(mt);
}


void initialize(vector<int> T, vector<int> H)
{
    init(T, H);
}

• 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