제출 #1254968

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

obstacles

#include "obstacles.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
int n,m,temp[maxn],hum[maxn],maxt[maxn],mint[maxn];
struct slog{
   int 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;
}
int stk;
slog get(int lg,int dg,int gde=1,int lc=1,int dc=stk){
   if(lg==lc and dg==dc)
      return st[gde];
   int 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);
}
int rod[maxn],vel[maxn];
int getp(int x){
   if(rod[x]==x)
      return x;
   rod[x]=getp(rod[x]);
   return rod[x];
}
void spoj(int a,int 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;
}
int najtemp(int x){
   int dg=1,gg=n,sred,res;
   while(dg<=gg){
      sred=(dg+gg)/2;
      if(mint[sred]>x){
         res=sred;
         dg=sred+1;
      }
      else
         gg=sred-1;
   }
   return maxt[res];
}
void resi(int l,int r,int lp,int rp){
   if(r<l)
      return;
   int m=get(l,r).mn;
  // cout<<"RESI "<<m<<" "<<hum[m]<<endl;
  // cout<<l<<" "<<r<<" "<<lp<<" "<<rp<<endl;
   if(hum[m]>=temp[1])
      return;
   int mt=najtemp(hum[m]);
   //cout<<mt<<endl;
   if(lp!=-1){
      int mx=get(lp,m).mx;
     // cout<<"LEFT hum "<<mx<<" temp "<<mt<<endl;
      if(mx<mt)
         spoj(m,lp);
   }
   if(rp!=-1){
      int mx=get(m,rp).mx;
     // cout<<"RIGHT hum "<<mx<<" temp "<<mt<<endl;
      if(mx<mt)
         spoj(m,rp);
   }
   resi(l,m-1,lp,m);
   resi(m+1,r,m,rp);
}
void initialize(std::vector<int> T, std::vector<int> H) {
   n=T.size();
   m=H.size();
   for(int i=1;i<=n;i++)
      temp[i]=T[i-1];
   for(int i=1;i<=m;i++)
      hum[i]=H[i-1];
   stk=1;
   while(stk<m)
      stk<<=1;
   for(int i=stk;i<stk+m;i++){
      st[i].mx=hum[i-stk+1];
      st[i].mn=i-stk+1;
   }
   for(int i=stk-1;i>=1;i--)
      st[i]=stspoj(st[i*2],st[i*2+1]);
   for(int i=1;i<=m;i++){
      rod[i]=i;
      vel[i]=1;
   }
   maxt[1]=mint[1]=temp[1];
   for(int i=2;i<=n;i++){
      maxt[i]=max(maxt[i-1],temp[i]);
      mint[i]=min(mint[i-1],temp[i]);
   }
   resi(1,m,-1,-1);
   return;
}

bool can_reach(int L, int R, int S, int D) {
   return getp(S+1)==getp(D+1);
}

• 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