제출 #1263886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263886		silentloop	장애물 (IOI25_obstacles)	C++20	83 / 100	1363 ms	46696 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;

const int MAXM=2e5+1;

vector<ll> segH, IH, DH, comp[MAXM], miT, maT;
vector<pair<ll,ll>>seg2H;
ll potT = 1, potH = 1, n, m, id[MAXM];
ll INF = LLONG_MAX;
vector<int>t,h;

ll calc(ll a, ll b, ll nod)
{
    if(IH[nod]>b||DH[nod]<a)
        return 0;
    if(IH[nod]>=a&&DH[nod]<=b)
        return segH[nod];
    return max(calc(a,b,nod*2),calc(a,b,nod*2+1));
}
pair<ll,ll> calcMi(ll a, ll b, ll nod)
{
    if(IH[nod]>b||DH[nod]<a)
        return {INF,0};
    if(IH[nod]>=a&&DH[nod]<=b)
        return seg2H[nod];
    pair<ll,ll>p1=calcMi(a,b,nod*2),p2=calcMi(a,b,nod*2+1);
    if(p1.fr<p2.fr)
        return p1;
    return p2;
}

void unionfind(ll x, ll y)
{
    ll a=id[x], b=id[y];
    if(a==b)
        return;
    if(sz(comp[a])<sz(comp[b]))
        swap(a,b);
    for(auto k:comp[b])
    {
        comp[a].pb(k);
        id[k]=a;
    }
}

void cons(ll x)
{
    if(t[0]<=h[x])
        return;
    ll l=0, r=n-1, piv, pos=0;
    while(l<=r)
    {
        piv=(l+r)/2;
        if(miT[piv]>h[x])
        {
            l=piv+1;
            pos=piv;
        }
        else
            r=piv-1;
    }

    ll ma=maT[pos];
    l=0, r=x;
    pos=x;
    while(l<=r)
    {
        piv=(l+r)/2;
        if(calc(piv+potH, x+potH,1)>=ma)
        {
            l=piv+1;
        }
        else
        {
            r=piv-1;
            pos=piv;
        }
    }
    l=x, r=m-1;
    ll pos2=x;
    while(l<=r)
    {
        piv=(l+r)/2;
        if(calc(x+potH, piv+potH,1)>=ma)
        {
            r=piv-1;
        }
        else
        {
            l=piv+1;
            pos2=piv;
        }
    }
    pair<ll,ll>p=calcMi(pos+potH,pos2+potH,1);

    unionfind(p.se,x);

}

void initialize(std::vector<int> T, std::vector<int> H)
{
    t=T;
    h=H;
    n = sz(T);
    miT.resize(n);
    maT.resize(n);
    miT[0]=T[0];
    maT[0]=T[0];
    for(ll i=1; i<n; i++)
    {
        miT[i]=min(miT[i-1],1ll*T[i]);
        maT[i]=max(maT[i-1],1ll*T[i]);
    }
    m = sz(H);
    ll i;
    while (potH < m)
        potH *= 2;
    segH.resize(potH*2, INF);
    seg2H.resize(potH*2,{INF,0});
    IH.resize(potH * 2);
    DH.resize(potH * 2);
    for (i = potH; i < potH * 2; i++)
        IH[i] = DH[i] = i;
    for (i = 0; i < m; i++)
    {
        seg2H[i+potH]={H[i],i};
        segH[i + potH] = H[i];
    }
    for (i = potH - 1; i > 0; i--)
    {
        IH[i] = IH[i * 2];
        DH[i] = DH[i * 2 + 1];
        segH[i]=max(segH[i*2],segH[i*2+1]);
        seg2H[i]=seg2H[i*2];
        if(seg2H[i].fr>seg2H[i*2+1].fr)
            seg2H[i]=seg2H[i*2+1];
    }
    for(i=0; i<m; i++)
    {
        comp[i]={i};
        id[i]=i;
    }
    for(i=0; i<m; i++)
        cons(i);

    return;
}

bool can_reach(int L, int R, int S, int D)
{
    return id[S]==id[D];
}

• 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