| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1307860 | exoworldgd | Obstacles for a Llama (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
#include "obstacles.h"
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
using ll=long long;
const int inf=1e9+1e5,LOG=20,BLOCK=1<<10;
int minr(const vector<int>&v,int a,int b){return a==b?inf:*min_element(v.begin()+a,v.begin()+b);}
struct SegTree{
int n;
vector<int>v,b;
SegTree():n(-1){}
SegTree(const vector<int>&vals){
n=(vals.size()+BLOCK-1)/BLOCK*BLOCK,v=vals;
while(v.size()^n)v.push_back(-inf);
b.resize(n/BLOCK);
for(int i=0;i<n/BLOCK;i++)b[i]=*min_element(v.begin()+i*BLOCK,v.begin()+(i+1)*BLOCK);
}
int query(int l,int r)const{
int lb=l/BLOCK,rb=r/BLOCK;
return lb==rb?minr(v,l,r):min({minr(v,l,BLOCK*(lb+1)),minr(b,lb+1,rb),minr(v,BLOCK*rb,r)});
}
int first_less(int i,int val)const{
int ib=i/BLOCK,k=ib+1;
for(int j=i;j<(ib+1)*BLOCK;j++)if(v[j]<val)return j;
while(k<b.size()&&b[k]>=val)k++;
for(int j=k*BLOCK;j<n;j++)if(v[j]<val)return j;
return n;
}
int last_less(int i,int val)const{
int ib=i/BLOCK,k=ib;
for(int j=i-1;j>=ib*BLOCK;j--)if(v[j]<val)return j;
while(k&&b[k-1]>=val)k--;
for(int j=k*BLOCK-1;j+1;j--)if(v[j]<val)return j;
return -1;
}
};
tuple<int,int,int>join(tuple<int,int,int>a,tuple<int,int,int>b){return{max(get<0>(a),get<0>(b)),min(get<1>(a),get<1>(b)),get<2>(b)};}
struct Forest{
vector<int>pos,dep;
vector<array<tuple<int,int,int>,LOG>>rmq;
int lca(int a,int b){
if(dep[a]>dep[b])swap(a,b);
for(int l=LOG-1;l+1;l--)if(dep[get<2>(rmq[b][l])]>=dep[a])b=get<2>(rmq[b][l]);
for(int l=LOG-1;l+1;l--)if(get<2>(rmq[a][l])!=get<2>(rmq[b][l]))a=get<2>(rmq[a][l]),b=get<2>(rmq[b][l]);
return a==b?a:(get<2>(rmq[a][0])==get<2>(rmq[b][0])?get<2>(rmq[a][0]):-1);
}
tuple<int,int,int>conn(int a,int b){
auto res=make_tuple(-inf,inf,a);
for(int l=LOG-1;l>=0;l--)if(dep[get<2>(rmq[get<2>(res)][l])]>=dep[b])res=join(res,rmq[get<2>(res)][l]);
return res;
}
}forest;
vector<tuple<int,int,int,int,int,int>>build(const vector<int>&t,const vector<int>&h){
int n=t.size(),m=h.size();
vector<int>mx={0},ord(m);
for(int i=1;i<n;i++)if(t[i]>t[mx.back()])mx.push_back(i);
iota(ord.begin(),ord.end(),0),sort(ord.begin(),ord.end(),[&](int i,int j){return h[i]>h[j];});
auto hinv=h;
for(auto&x:hinv)x*=-1;
const auto hrmq=SegTree(h),hivrmq=SegTree(hinv),trmq=SegTree(t);
map<int,int>act;
vector<tuple<int,int,int,int,int,int>>lyr;
for(auto i:mx){
int tmp=t[i];
vector<int>ec;
while(!ord.empty()&&h[ord.back()]<tmp)ec.push_back(ord.back()),ord.pop_back();
set<pair<int,int>>rng;
for(auto c:ec)rng.insert({hivrmq.last_less(c,1-tmp)+1,hivrmq.first_less(c,1-tmp)});
for(auto&[l,r]:rng){
int idx=lyr.size();
while(1){
it=act.lower_bound(l);
if(it==act.end()||it->first>=r)break;
auto&ch=lyr[it->second];
int mt=trmq.query(get<0>(ch),i+1);
if(mt>hrmq.query(get<1>(ch),get<2>(ch)))get<4>(ch)=hrmq.first_less(get<1>(ch),mt),get<5>(ch)=hrmq.last_less(get<2>(ch),mt),get<3>(ch)=idx;
act.erase(it);
}
act[l]=idx,lyr.push_back({i,l,r,idx,-inf,inf});
}
}
return lyr;
}
void initialize(vector<int>T,vector<int>H){
auto lyr=build(T,H);
vector<int>pos(H.size(),-1);
for(int i=0;i<lyr.size();i++)if(get<0>(lyr[i])==0)for(int j=get<1>(lyr[i]);j<get<2>(lyr[i]);j++)pos[j]=i;
vector<array<tuple<int,int,int>,LOG>>rmq(lyr.size());
vector<int>dep(lyr.size());
for(int i=lyr.size()-1;i+1;i--){
rmq[i][0]={get<4>(lyr[i]),get<5>(lyr[i]),get<3>(lyr[i])},dep[i]=get<3>(lyr[i])==i?0:1+dep[get<3>(lyr[i])];
for(int l=0;l<LOG-1;l++)rmq[i][l+1]=join(rmq[i][l],rmq[get<2>(rmq[i][l])][l]);
}
forest.pos=pos,forest.dep=dep,forest.rmq=rmq;
}
bool can_reach(int L,int R,int S,int D){
if(S>D)swap(S,D);
int a=forest.pos[S],b=forest.pos[D],c=forest.lca(a,b);
return c^-1&&get<1>(forest.conn(a,c))>=L&&get<0>(forest.conn(b,c))<=R;
}