제출 #1255085

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

obstacles

#include "obstacles.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2e5+5;
ll n,m,temp[maxn],hum[maxn],maxt[maxn],mll[maxn],lpar[20][maxn],rpar[20][maxn],lval[20][maxn],rval[20][maxn],dubl[maxn],dubr[maxn];
struct slog{
   ll mn,mx;
} st[4*maxn];
slog stspoj(slog a,slog b){
   slog r;
   if(hum[a.mn]<hum[b.mn])
      r.mn=a.mn;
   else
      r.mn=b.mn;
   r.mx=max(a.mx,b.mx);
   return r;
}
ll stk;
slog get(ll lg,ll dg,ll gde=1,ll lc=1,ll dc=stk){
   if(lg==lc and dg==dc)
      return st[gde];
   ll sred=(lc+dc)/2;
   if(dg<=sred)
      return get(lg,dg,gde*2,lc,sred);
   if(lg>sred)
      return get(lg,dg,gde*2+1,sred+1,dc);
   slog v1,v2;
   v1=get(lg,sred,gde*2,lc,sred);
   v2=get(sred+1,dg,gde*2+1,sred+1,dc);
   return stspoj(v1,v2);
}
ll rod[maxn],vel[maxn];
ll getp(ll x){
   if(rod[x]==x)
      return x;
   rod[x]=getp(rod[x]);
   return rod[x];
}
void spoj(ll a,ll b){
   a=getp(a);
   b=getp(b);
   if(a==b)
      return;
   if(vel[a]<vel[b])
      swap(a,b);
   vel[a]=max(vel[a],vel[b]+1);
   rod[b]=a;
   return;
}
ll najtemp(ll x){
   ll dg=1,gg=n,sred,res;
   while(dg<=gg){
      sred=(dg+gg)/2;
      if(mll[sred]>x){
         res=sred;
         dg=sred+1;
      }
      else
         gg=sred-1;
   }
   return maxt[res];
}
void resi(ll l,ll r,ll lp,ll rp){
   if(r<l)
      return;
   ll m=get(l,r).mn;
  // cout<<"RESI "<<m<<" "<<hum[m]<<endl;
  // cout<<l<<" "<<r<<" "<<lp<<" "<<rp<<endl;
   if(hum[m]>=temp[1])
      return;
   ll mt=najtemp(hum[m]);
   bool ml=false,mr=false;
   //cout<<mt<<endl;
   if(lp!=-1){
      ll mx=get(lp,m).mx;
     // cout<<"LEFT hum "<<mx<<" temp "<<mt<<endl;
      if(mx<mt){
         spoj(m,lp);
         ml=true;
      }
   }
   if(rp!=-1){
      ll mx=get(m,rp).mx;
     // cout<<"RIGHT hum "<<mx<<" temp "<<mt<<endl;
      if(mx<mt){
         spoj(m,rp);
         mr=true;
      }
   }



   if(ml)
      lpar[0][m]=lp;
   else if(mr)
      lpar[0][m]=rp;

   if(mr)
      rpar[0][m]=rp;
   else if(ml)
      rpar[0][m]=lp;


   resi(l,m-1,lp,m);
   resi(m+1,r,m,rp);
}
bool lbio[maxn],rbio[maxn];
vector<ll> lstab[maxn],rstab[maxn];
void dfsl(ll gde,ll d){
   if(lbio[gde])
      return;
   lbio[gde]=true;
   dubl[gde]=d;
   for(ll x:lstab[gde])
      dfsl(x,d+1);
}
void dfsr(ll gde,ll d){
   if(rbio[gde])
      return;
   rbio[gde]=true;
   dubr[gde]=d;
   for(ll x:rstab[gde])
      dfsr(x,d+1);
}
ll liftl(ll x,ll d){
   ll ans=x;
   for(ll j=18;j>=0;j--){
      ll ko=lpar[j][x];
      if(dubl[ko]>=d){
         ans=min(ans,lval[j][x]);
         x=ko;
      }
   }
   return ans;
}
ll liftr(ll x,ll d){
   ll ans=x;
   for(ll j=18;j>=0;j--){
      ll ko=rpar[j][x];
      if(dubr[ko]>=d){
         ans=max(ans,rval[j][x]);
         x=ko;
      }
   }
   return ans;
}
vector<ll> red;
bool cmp(ll a,ll b){
   return hum[a]<hum[b];
}
void initialize(std::vector<int> T, std::vector<int> H) {
   n=T.size();
   m=H.size();
   for(ll i=1;i<=n;i++)
      temp[i]=T[i-1];
   for(ll i=1;i<=m;i++)
      hum[i]=H[i-1];
   for(ll i=1;i<=m;i++)
      lpar[0][i]=rpar[0][i]=i;
   stk=1;
   while(stk<m)
      stk<<=1;
   for(ll i=stk;i<stk+m;i++){
      st[i].mx=hum[i-stk+1];
      st[i].mn=i-stk+1;
   }
   for(ll i=stk-1;i>=1;i--)
      st[i]=stspoj(st[i*2],st[i*2+1]);
   for(ll i=1;i<=m;i++){
      rod[i]=i;
      vel[i]=1;
   }
   maxt[1]=mll[1]=temp[1];
   for(ll i=2;i<=n;i++){
      maxt[i]=max(maxt[i-1],temp[i]);
      mll[i]=min(mll[i-1],temp[i]);
   }
   resi(1,m,-1,-1);


   for(ll i=1;i<=m;i++){
      lstab[lpar[0][i]].push_back(i);
      rstab[rpar[0][i]].push_back(i);
   }
   for(ll i=1;i<=m;i++)
      red.push_back(i);
   sort(red.begin(),red.end(),cmp);

   for(ll i:red){
      dfsl(i,0);
      dfsr(i,0);
   }
   for(ll i=0;i<=m;i++){
      lval[0][i]=rval[0][i]=i;
   }
   for(ll j=1;j<=18;j++){
      for(ll i=1;i<=m;i++){
         lpar[j][i]=lpar[j-1][lpar[j-1][i]];
         lval[j][i]=min(lval[j-1][i],lval[j-1][lpar[j-1][i]]);

         rpar[j][i]=rpar[j-1][rpar[j-1][i]];
         rval[j][i]=max(rval[j-1][i],rval[j-1][rpar[j-1][i]]);
      }
   }/*
   for(ll i=1;i<=m;i++){
      cout<<i<<" "<<lpar[0][i]<<endl;
   }*/
   return;
}

bool can_reach(int L, int R, int S, int D) {
   S++;
   D++;
   if(S>D)
      swap(S,D);
   if(S==D)
      return true;
   if(getp(S)!=getp(D))
      return false;
   L++;
   R++;
   ll mid=get(S,D).mn;
   ll l=liftl(S,dubl[mid]);
   ll r=liftr(D,dubr[mid]);
 //  cout<<l<<" "<<r<<endl;
   return L<=l and r<=R;
}

• 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