Submission #1258549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258549		medmdg	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	155 ms	37180 KiB

obstacles

#include "obstacles.h"
#include<bits/stdc++.h>
using namespace std;
#define mk(a,b) make_pair(a,b)
vector<int> par,w;
int find(int ind){
  if(par[ind]==ind)return ind;
  return par[ind]=find(par[ind]);
}
void join(int u,int v){
  u=find(u),v=find(v);
  if(u==v)return;
  if(w[u]<w[v])swap(u,v);
  par[v]=u;
  w[u]+=w[v];
}
int maRange(int l,int r, vector<vector<int>>&ma){
  int t=log2(r-l+1);
  int ans=ma[l][t];
  ans=max(ans,ma[r+1-(1<<t)][t]);
  return ans;

}
void initialize(vector<int> T, vector<int> H) {
  int m=H.size(),n=T.size();
  par.clear();
  par.resize(m);
  w.resize(m);
  for(int i=0;i<H.size();i++){
    par[i]=i;
    w[i]=1;
  }
  vector<int> maxT(n,0);
  maxT[0]=T[0];
  for(int i=1;i<n;i++){
    maxT[i]=max(maxT[i-1],T[i]);
  }
  vector<int> nH(m,-1),pH(m,-1);
  vector<int> q;
  for(int i=m-1;i>=0;i--){
    while(q.size()&&H[i]<H[q.back()]){
      q.pop_back();
    }
    if(q.size())  nH[i]=q.back();
    q.push_back(i);
  }
  q.clear();
  for(int i=0;i<m;i++){
    while(q.size()&&H[i]<H[q.back()]){
      q.pop_back();
    }
    if(q.size())  pH[i]=q.back();
    q.push_back(i);
  }

  vector<vector<int>> ma(m,vector<int>(20,1e9+1));
  for(int i=0;i<m;i++)  ma[i][0]=H[i];
  for(int i=m-1;i>=0;i--){
    for(int j=0;j<19;j++){
      int nxt=i+(1<<j);
      if(nxt<m)ma[i][j+1]=max(ma[i][j],ma[nxt][j]);
      else break;
    }
  }
  
  vector<pair<int,int>> s;
  for(int i=0;i<m;i++){
    s.push_back(mk(H[i],i));
  }
  sort(s.rbegin(),s.rend());
  vector<int> rw(m,-1);
  int cur=-1;
  for(auto &x:s){
    while(cur<m-1 && x.first<T[cur+1])cur++;
    if(cur==-1)rw[x.second]=cur;
    else rw[x.second]=maxT[cur];
    x.first=rw[x.second];
  }
  for(auto x:s){
    //check right
    int ind=x.second,val=x.first;
    if(nH[ind]!=-1){
      int nex=nH[ind];
      if(rw[ind]>maRange(ind,nex,ma)){
        join(ind,nex);
      }
    }
    //check left
    if(pH[ind]!=-1){
      int nex=pH[ind];
      if(rw[ind]>maRange(nex,ind,ma)){
        join(ind,nex);
      }
    }
  }
}

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