제출 #1264376

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264376		abdelhakim	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	152 ms	55984 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
#define ll long long
#define inf 1e17
#define dbg(x) cerr<<#x<< ' '<<x<<endl;
using namespace std;

vector<ll> t;
vector<ll> h;
vector<ll> par;
vector<ll> sz;
vector<ll> maxt;
vector<ll> mint;
vector<vector<ll>> sp;
int lg[200001];
ll findrep(ll node)
{
  if(par[node]==node)
  {
    return node;
  }
  return par[node]=findrep(par[node]);
}
void unionsets(ll u, ll v)
{
  u=findrep(u);
  v=findrep(v);
  if(u==v)
  {
    return;
  }
  if(sz[u] < sz[v]) swap(u,v);
  par[v]=u;
  sz[u]+=sz[v];
}
ll n,m;
bool free(ll x, ll y)
{
  return t[y] > h[x];
}
ll maxh(ll l, ll r)
{
  ll sze=lg[r-l+1];
  return max(sp[l][sze],sp[r-(1<<sze)+1][sze]);
}
ll akbarT(ll c)
{
  ll l=0;
  ll r=n-1;
  ll ab3ad=0;
  while(l<=r)
  {
    ll mid=(l+r)/2;
    if(mint[mid]>h[c])
    {
      ab3ad=mid;
      l=mid+1;
    }
    else
    {
      r=mid-1;
    }
  }
  return maxt[ab3ad];
}
void initialize(std::vector<int> T, std::vector<int> H) {
  t.assign(T.begin(), T.end());
  h.assign(H.begin(), H.end());
  n = t.size();
  m = h.size();
  par.resize(m);
  maxt.resize(n);
  mint.resize(n);
  sz.resize(m);
  sp.assign(m,vector<ll>(18));
  lg[1]=0;
  for (int i=2;i<=200000;i++)
  {
    lg[i]=lg[i/2]+1;
  }
  for (int i=0;i<m;i++)
  {
    par[i]=i;
    sz[i]=1;
  }
  for (int i=0;i<n;i++)
  {
    if(i==0)
    {
      maxt[i]=mint[i]=t[i];
    }
    else
    {
      maxt[i]=max(maxt[i-1],t[i]);
      mint[i]=min(mint[i-1],t[i]);
    }
  }
  for (int j=0;j<=17;j++)
  {
    for (int i=0;i+(1<<j)<=m && i<m;i++)
    {
      if(j==0)
      {
        sp[i][j]=h[i];
      }
      else
      {
        sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
      }
    }
  }
  stack<pair<ll,ll>> st;
  for (int i=0;i<m;i++)
  {
    while(st.size() && st.top().first > h[i])
    {
      st.pop();
    }
    if(!st.empty())
    {
      ll nxt=st.top().second;
      ll kbir=akbarT(i);
      if(kbir > maxh(nxt,i))
      {
        unionsets(i,nxt);
      }
    }
    st.push({h[i],i});
  }
  while(st.size()) st.pop();
  for (int i=m-1;i>=0;i--)
  {
    while(st.size() && st.top().first > h[i])
    {
      st.pop();
    }
    if(!st.empty())
    {
      ll nxt=st.top().second;
      ll kbir=akbarT(i);
      if(kbir > maxh(i,nxt))
      {
        unionsets(i,nxt);
      }
    }
    st.push({h[i],i});
  }
  return;
}

bool can_reach(int L, int R, int S, int D) {
  return findrep(S)==findrep(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