제출 #1269518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269518		SamAnd	장애물 (IOI25_obstacles)	C++20	83 / 100	1352 ms	65748 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005, INF = 1000000009, k = 18;

int n, m;
int p[N], pl[N], pr[N];

int maxh[N * 4];
pair<int, int> minh[N * 4];
void bil(const vector<int>& H, int tl, int tr, int pos)
{
    if (tl == tr)
    {
        maxh[pos] = H[tl];
        minh[pos] = m_p(H[tl], tl);
        return;
    }
    int m = (tl + tr) / 2;
    bil(H, tl, m, pos * 2);
    bil(H, m + 1, tr, pos * 2 + 1);
    maxh[pos] = max(maxh[pos * 2], maxh[pos * 2 + 1]);
    minh[pos] = min(minh[pos * 2], minh[pos * 2 + 1]);
}

int qrymax(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return -1;
    if (tl == l && tr == r)
        return maxh[pos];
    int m = (tl + tr) / 2;
    return max(qrymax(tl, m, l, min(m, r), pos * 2),
               qrymax(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

pair<int, int> qrymin(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return m_p(INF, INF);
    if (tl == l && tr == r)
        return minh[pos];
    int m = (tl + tr) / 2;
    return min(qrymin(tl, m, l, min(m, r), pos * 2),
               qrymin(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

vector<int> gg[N];
int pp[N][k];
void dfs(int x, int p)
{
    pp[x][0] = p;
    for (int i = 1; i < k; ++i)
        pp[x][i] = pp[pp[x][i - 1]][i - 1];
    for (int i = 0; i < gg[x].size(); ++i)
    {
        int h = gg[x][i];
        if (h == p)
            continue;
        dfs(h, x);
    }
}

int ppl[N][k], ppr[N][k];

void initialize(std::vector<int> T, std::vector<int> H)
{
    n = sz(T);
    m = sz(H);

    vector<int> mint(sz(T)), maxt(sz(T));
    mint[0] = T[0];
    for (int i = 1; i < sz(T); ++i)
        mint[i] = min(mint[i - 1], T[i]);
    maxt[0] = T[0];
    for (int i = 1; i < sz(T); ++i)
        maxt[i] = max(maxt[i - 1], T[i]);
    bil(H, 0, m - 1, 1);

    for (int j = 0; j < m; ++j)
    {
        if (H[j] >= T[0])
        {
            p[j] = pl[j] = pr[j] = j;
            continue;
        }
        int l = 1, r = n - 1;
        int t = T[0];
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (mint[mid] > H[j])
            {
                t = maxt[mid];
                l = mid + 1;
            }
            else
                r = mid - 1;
        }

        l = j;
        r = m - 1;
        int ur = -1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (qrymax(0, m - 1, j, mid, 1) < t)
            {
                ur = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        assert(ur != -1);

        l = 0;
        r = j;
        int ul = -1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (qrymax(0, m - 1, mid, j, 1) < t)
            {
                ul = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        assert(ul != -1);

        pair<int, int> pl = qrymin(0, m - 1, ul, j, 1);
        pair<int, int> pr = qrymin(0, m - 1, j, ur, 1);
        ::pl[j] = pl.se;
        ::pr[j] = pr.se;
        p[j] = min(pl, pr).se;
    }

    for (int j = 0; j < m; ++j)
    {
        if (j != pl[j])
            gg[pl[j]].push_back(j);
    }
    for (int j = 0; j < m; ++j)
    {
        if (j == pl[j])
            dfs(j, j);
    }
    memcpy(ppl, pp, sizeof pp);

    for (int j = 0; j < m; ++j)
        gg[j].clear();
    for (int j = 0; j < m; ++j)
    {
        if (j != pr[j])
            gg[pr[j]].push_back(j);
    }
    for (int j = 0; j < m; ++j)
    {
        if (j == pr[j])
            dfs(j, j);
    }
    memcpy(ppr, pp, sizeof pp);

    for (int j = 0; j < m; ++j)
        gg[j].clear();
    for (int j = 0; j < m; ++j)
    {
        if (j != p[j])
            gg[p[j]].push_back(j);
    }
    for (int j = 0; j < m; ++j)
    {
        if (j == p[j])
            dfs(j, j);
    }
}

int go(int x, int l, int r)
{
    for (int i = k - 1; i >= 0; --i)
    {
        if (l <= pp[x][i] && pp[x][i] <= r)
        {
            x = pp[x][i];
        }
    }
    assert(pp[x][0] == x || !(l <= pp[x][0] && pp[x][0] <= r));
    if (pp[x][0] == x)
        return x;
    if (pp[x][0] < l)
    {
        x = qrymin(0, m - 1, l, x, 1).se;
        for (int i = k - 1; i >= 0; --i)
        {
            if (ppr[x][i] <= r)
            {
                x = ppr[x][i];
            }
        }
        return x;
    }
    assert(pp[x][0] > r);
    {
        x = qrymin(0, m - 1, x, r, 1).se;
        for (int i = k - 1; i >= 0; --i)
        {
            if (ppl[x][i] >= l)
            {
                x = ppl[x][i];
            }
        }
        return x;
    }
}

bool can_reach(int L, int R, int S, int D)
{
    return go(S, L, R) == go(D, L, R);
}

/*
3 4
2 1 3
0 1 2 0
2
0 3 1 3
1 3 1 3
*/

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