Submission #1261231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261231		Faggi	장애물 (IOI25_obstacles)	C++20	0 / 100	60 ms	27448 KiB

obstacles

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
vector<ll> t, h, seg, I, D;
vector<pair<ll, ll>> seg2;

const int MAXN = 2e1 + 1;
const int LOG = 20;

ll iz[MAXN][LOG], der[MAXN][LOG], maIz[MAXN][LOG], maDer[MAXN][LOG];
ll n, m, pot = 1;
void initialize(std::vector<int> T, std::vector<int> H)
{
    for (auto k : T)
        t.pb(k);
    for (auto k : H)
        h.pb(k);
    while (pot < sz(h))
        pot *= 2;
    seg.resize(pot * 2, 0);
    seg2.resize(pot * 2, {LLONG_MAX, -1});
    I.resize(pot * 2);
    D.resize(pot * 2);
    ll i;
    for (i = pot; i < pot * 2; i++)
        I[i] = D[i] = i;
    for (i = 0; i < sz(H); i++)
    {
        seg[i + pot] = H[i];
        seg2[i + pot] = {H[i], i};
    }
    for (i = pot - 1; i > 0; i--)
    {
        I[i] = I[i * 2];
        D[i] = D[i * 2 + 1];
        seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
        seg2[i] = seg2[i * 2];
        if (seg2[i * 2 + 1].fr < seg2[i].fr)
            seg2[i] = seg2[i * 2 + 1];
    }
    ll j;
    for (j = 0; j < sz(H); j++)
    {
        iz[j][0]=max(0ll,j-1);
        der[j][0]=j+1;
        maIz[j][0]=H[j];
        if(j-1>=0)
            maIz[j][0]=max(maIz[j][0],h[j-1]);
        maDer[j][0]=h[j];
        if(j+1<sz(H))
            maDer[j][0]=max(maDer[j][0],h[j+1]);
    }
    for (i = 1; i < LOG; i++)
    {
        for (j = 0; j < sz(H); j++)
        {
            iz[j][i]=iz[iz[j][i-1]][i-1];
            maIz[j][i]=max(maIz[j][i-1],maIz[iz[j][i-1]][i-1]);
        }
        for (j = sz(H)-1; j>=0; j--)
        {
            der[j][i]=der[der[j][i-1]][i-1];
            maDer[j][i]=max(maDer[j][i-1],maDer[der[j][i-1]][i-1]);
        }
    }
    return;
}

ll calc(ll a, ll b, ll nod)
{
    if (I[nod] > b || D[nod] < a)
        return 0;
    if (I[nod] >= a && D[nod] <= b)
        return seg[nod];
    return max(calc(a, b, nod * 2), calc(a, b, nod * 2 + 1));
}

pair<ll, ll> calc2(ll a, ll b, ll nod)
{
    if (I[nod] > b || D[nod] < a)
        return {LLONG_MAX, -1};
    if (I[nod] >= a && D[nod] <= b)
        return seg2[nod];
    pair<ll, ll> r1, r2;
    r1 = calc2(a, b, nod * 2);
    r2 = calc2(a, b, nod * 2 + 1);
    if (r1.fr > r2.fr)
        return r2;
    return r1;
}

bool con(ll i, ll ja, ll jb)
{
    ll ma = 0, j;
    ma = calc(ja + pot, jb + pot, 1);
    if (ma >= t[i])
        return 0;
    return 1;
}

ll minR(ll i, ll j)
{
    ll mi = LLONG_MAX, pj = -1, k, l = 0, r = j, piv, ma, pos = -1, act;
    act=j;
    for(k=LOG-1; k>=0; k--)
    {
        if(maIz[act][k]<t[i])
            act=iz[act][k];
    }
    pos=act;
    pair<ll, ll> ret;
    if (pos != -1)
    {
        ret = calc2(pos + pot, j + pot, 1);
        if (mi > ret.fr)
        {
            mi = ret.fr;
            pj = ret.se;
        }
    }
    pos = -1;
    act=j;
    for(k=LOG-1; k>=0; k--)
    {
        if(maDer[act][k]<t[i])
            act=der[act][k];
    }
    if (pos != -1)
    {
        ret = calc2(j + pot, pos + pot, 1);
        if (mi > ret.fr)
        {
            mi = ret.fr;
            pj = ret.se;
        }
    }
    return pj;
}

bool can_reach(int L, int R, int S, int D)
{
    n = sz(t);
    m = sz(h);
    ll i;
    if (S > D)
        swap(S, D);
    for (i = 0; i < n; i++)
    {
        if (con(i, S, D))
            return 1;
        if (i + 1 < n)
        {
            S = minR(i, S);
            D = minR(i, D);
            if (S == -1 || D == -1)
                return 0;
        }
    }
    return 0;
}

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