Submission #1252604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252604		bachhoangxuan	Obstacles for a Llama (IOI25_obstacles)	C++20	21 / 100	2100 ms	87724 KiB

obstacles

#include "obstacles.h"
#include<bits/stdc++.h>
using namespace std;
const int LG=20;

vector<int> a;
vector<vector<int>> sl,sr,sn,ln,rn;

void initialize(std::vector<int> T, std::vector<int> H) {
  int N=(int)T.size(),M=(int)H.size();
  
  vector<int> mn(N),mx(N);
  for(int i=0;i<N;i++){
    mn[i]=mx[i]=T[i];
    if(i){
      mn[i]=min(mn[i],mn[i-1]);
      mx[i]=max(mx[i],mx[i-1]);
    }
  }

  a.assign(M,-1);
  for(int i=0;i<M;i++){
    int p=lower_bound(mn.begin(),mn.end(),H[i],[&](int x,int y){
      return x>y;
    })-mn.begin();
    if(p) a[i]=mx[p-1];
  }

  vector<int> lt(M),rt(M);
  vector<pair<int,int>> v;
  for(int i=0;i<M;i++){
    int val=H[i];
    while(!v.empty() && H[v.back().first]>H[i]) val=max(val,v.back().second),v.pop_back();
    lt[i]=i;
    if(!v.empty() && a[i]>val) lt[i]=v.back().first;
    v.push_back({i,val});
  }
  v.clear();
  for(int i=M-1;i>=0;i--){
    int val=H[i];
    while(!v.empty() && H[v.back().first]>=H[i]) val=max(val,v.back().second),v.pop_back();
    rt[i]=i;
    if(!v.empty() && a[i]>val) rt[i]=v.back().first;
    v.push_back({i,val});
  }

  vector<int> nxt(M);
  for(int i=0;i<M;i++){
    if(lt[i]==i || rt[i]==i) nxt[i]=lt[i]^rt[i]^i;
    else{
      pair<int,int> L={H[lt[i]],lt[i]},R={H[rt[i]],rt[i]};
      if(L>R) nxt[i]=L.second;
      else nxt[i]=R.second;
    }
  }

  sl.assign(LG,vector<int>(M,0));
  sr.assign(LG,vector<int>(M,0));
  sn.assign(LG,vector<int>(M,0));
  ln.assign(LG,vector<int>(M,0));
  rn.assign(LG,vector<int>(M,0));
  sl[0]=lt,sr[0]=rt,sn[0]=nxt;
  for(int i=0;i<M;i++) ln[0][i]=min(i,nxt[i]),rn[0][i]=max(i,nxt[i]);
  
  for(int i=1;i<LG;i++){
    for(int j=0;j<M;j++){
      sl[i][j]=sl[i-1][sl[i-1][j]];
      sr[i][j]=sr[i-1][sr[i-1][j]];
      sn[i][j]=sn[i-1][sn[i-1][j]];
      ln[i][j]=min(ln[i-1][j],ln[i-1][sn[i-1][j]]);
      rn[i][j]=max(rn[i-1][j],rn[i-1][sn[i-1][j]]);
    }
  }
}

bool can_reach(int L, int R, int S,int D) {
  if(min(a[S],a[D])==-1) return false;
  auto f = [&](int A){
    int lA=A,rA=A;
    for(int i=LG-1;i>=0;i--){
      int nA=sn[i][A],nlA=min(lA,ln[i][A]),nrA=max(rA,rn[i][A]);
      if(L<=nlA && nrA<=R) A=nA,lA=nlA,rA=nrA;
    }
    for(int i=LG-1;i>=0;i--){
      int nA=sl[i][A];
      if(L<=nA) A=nA;
    }
    for(int i=LG-1;i>=0;i--){
      int nA=sr[i][A];
      if(nA<=R) A=nA;
    }
    return A;
  };
  return f(S)==f(D);
}

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