Submission #1255004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255004		tosivanmak	Obstacles for a Llama (IOI25_obstacles)	C++20	100 / 100	441 ms	210616 KiB

obstacles

#include<bits/stdc++.h>
#ifndef LOCAL
#include "obstacles.h"
#endif
using namespace std;
#define ll long long

vector<ll>adj[200005];
bool vis[200005];
ll lft[200005][20];
ll mini[200005][20],maxi[200005][20];
ll dep[200005];
void dfs(ll s){
    vis[s]=1;
    for(auto& u: adj[s]){
        if(!vis[u]){
            dep[u]=dep[s]+1;
            lft[u][0]=s;
            mini[u][0]=maxi[u][0]=s;
            dfs(u);
        }
    }
}
struct DSU{
    vector<ll>fa,siz;
    void init(ll n){
        fa.resize(n+5); siz.resize(n+5);
        for(int i=0;i<=n;i++)fa[i]=i,siz[i]=1;
    }
    ll rt(ll x){
        if(fa[x]==x)return x;
        return fa[x]=rt(fa[x]);
    }
    void unite(ll u, ll v){
        // cout<<"Add edge "<<u<<" "<<v<<'\n';
        adj[u].push_back(v); adj[v].push_back(u);
        u=rt(u); v=rt(v);
        if(u==v)return;
        if(siz[u]<siz[v])swap(u,v);
        siz[u]+=siz[v]; fa[v]=u;
    }
    bool connected(ll u, ll v){
        return (rt(u)==rt(v));
    }
}d;

struct Set{
    vector<ll>fa,siz,l,r;
    vector<set<ll> >hv;
    void init(ll n){
        siz.resize(n+5); fa.resize(n+5); l.resize(n+5);
        r.resize(n+5); hv.resize(n+5);
        for(int i=0;i<=n;i++){
            siz[i]=1; fa[i]=i; l[i]=i; r[i]=i;
        }
    }
    void add(ll x){
        // cout<<"Inserted "<<x<<'\n';
        hv[x].insert(x);
    }
    ll rt(ll x){
        if(fa[x]==x)return x;
        return fa[x]=rt(fa[x]);
    }
    void unite(ll u, ll v){
        // cout<<"Join "<<u<<" "<<v<<'\n';
        u=rt(u); v=rt(v);
        if(siz[u]<siz[v])swap(u,v);
        siz[u]+=siz[v]; fa[v]=u;
        l[u]=min(l[u],l[v]); r[u]=max(r[u],r[v]);
        if(hv[u].size()==0||hv[v].size()==0){

        }
        else{
            if(u<v){
                d.unite(*hv[u].rbegin(),*hv[v].begin());
            }
            else{
                // cout<<u<<" "<<v<<'\n';
                // cout<<"hi "<<*hv[v].rbegin()<<" "<<*hv[u].begin()<<'\n';
                d.unite(*hv[v].rbegin(),*hv[u].begin());
            }
        }
        for(auto& k: hv[v])hv[u].insert(k);
    }
    void del(ll x){
        ll r=rt(x);
        if(hv[r].empty())return;
        if(*hv[r].rbegin()<x)return;
        ll bruh=*hv[r].lower_bound(x);
        if(bruh!=x)return;
        hv[r].erase(x);
    }
}st;
ll n,m;
vector<ll>reachable(200005),entering(200005);

vector<bool>opened(200005,false);
void modify(ll x, ll m, bool add){
    if(add)st.add(x);
    if(x==0){
        if(!opened[x+1]){
        }
        else{
            st.unite(x,x+1);
        }
    }
    else if(x==m-1){
        if(opened[x-1])st.unite(x,x-1);
    }
    else{
        if(opened[x+1])st.unite(x,x+1);
        if(opened[x-1])st.unite(x,x-1);
    }
    opened[x]=1;
}
void erase(ll x){
    // cout<<"Erased "<<x<<'\n';
    st.del(x);
}
pair<ll,ll> bl(ll u, ll v){
    if(dep[u]<dep[v]){
        swap(u,v);
    }
    ll minn=1e18; ll maxx=-1e18;
    ll req=dep[u]-dep[v];
    for(int i=0;i<=19;i++){
        if(req&(1LL<<i)){
            maxx=max(maxx,maxi[u][i]); minn=min(minn,mini[u][i]); u=lft[u][i];
        }
    }
    if(u==v)return {minn,maxx};
    for(int i=19;i>=0;i--){
        if(lft[u][i]==lft[v][i])continue;
        maxx=max({maxx,maxi[u][i],maxi[v][i]});
        minn=min({minn,mini[u][i],mini[v][i]});
        u=lft[u][i],v=lft[v][i];
    }
    return {min(minn,lft[u][0]),max(maxx,lft[v][0])};
}
void initialize(vector<int> T, vector<int> H){
    n=T.size(); m=H.size();
    st.init(m); d.init(m);
    // T[i]>H[j]: can step on  
    vector<ll>mink(n+5);
    for(int i=0;i<n;i++){
        mink[i]=T[i];
        if(i!=0){
            mink[i]=min(mink[i],mink[i-1]);
        }
    }
    for(int i=0;i<m;i++){
        ll l=0,r=n-1;
        if(mink[n-1]>H[i]){
            reachable[i]=n-1;
        }
        else if(mink[0]<=H[i]){
            reachable[i]=-1;
        }
        else{
            while(l<r){
                ll mid=(l+r+1)>>1;
                if(mink[mid]>H[i])l=mid;
                else r=mid-1;
            }
            reachable[i]=l;
        }
    }
    // row: T array, column, H array
    // T[i]>H[j]: can step on
    ll maxx=-1;
    vector<pair<ll,ll> >rows;
    for(int i=0;i<n;i++){
        if(T[i]>maxx){
            rows.push_back({T[i],i}); maxx=T[i];
        }
    }
    vector<ll>arrays[rows.size()+5];
    vector<ll>dels[rows.size()+5];
    for(int i=0;i<m;i++){
        if(reachable[i]==-1)continue;
        ll req=reachable[i]+1;
        // when rows[l].second>=req 
        if(req>rows[rows.size()-1].second)continue;
        ll l=0,r=rows.size()-1;
        while(l<r){
            ll mid=(l+r)>>1;
            if(rows[mid].second>=req)r=mid;
            else l=mid+1;
        }
        dels[l].push_back(i);
    }
    for(int i=0;i<m;i++){
        if(H[i]>=rows[rows.size()-1].first){
            continue;
        }
        ll l=0,r=rows.size()-1;
        while(l<r){
            ll mid=(l+r)>>1;
            if(rows[mid].first>H[i])r=mid;
            else l=mid+1;
        }
        arrays[l].push_back(i);
    }
    for(auto& u: arrays[0]){
        modify(u,m,1);
    }
    for(int i=1;i<(int)rows.size();i++){
        for(auto& u: dels[i]){
            erase(u);
        }
        for(auto& u: arrays[i]){
            modify(u,m,0);
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<=19;j++){
            mini[i][j]=maxi[i][j]=-1;
            lft[i][j]=-1;
        }
    }
    for(int i=0;i<m;i++){
        if(!vis[i]){
            dfs(i);
        }
    }
    for(int j=1;j<=19;j++){
        for(int i=0;i<m;i++){
            if(lft[i][j-1]==-1)continue;
            if(lft[lft[i][j-1]][j-1]==-1)continue;
            ll nxt=lft[i][j-1];
            lft[i][j]=lft[lft[i][j-1]][j-1];
            maxi[i][j]=max(maxi[i][j-1],maxi[nxt][j-1]);
            mini[i][j]=min(mini[i][j-1],mini[nxt][j-1]);
        }
    }
}
bool can_reach(int L, int R, int S, int D){
    if(!d.connected(S,D))return 0;
    pair<ll,ll> val=bl(S,D);
    if(val.first>=L&&val.second<=R)return 1;
    return 0;
}

#ifdef LOCAL
int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));
  std::vector<int> T(N), H(M);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &T[i]));
  for (int i = 0; i < M; i++)
    assert(1 == scanf("%d", &H[i]));

  int Q;
  assert(1 == scanf("%d", &Q));
  std::vector<int> L(Q), R(Q), S(Q), D(Q);
  for (int i = 0; i < Q; i++)
    assert(4 == scanf("%d %d %d %d", &L[i], &R[i], &S[i], &D[i]));

  fclose(stdin);

  std::vector<bool> A(Q);

  initialize(T, H);

  for (int i = 0; i < Q; i++)
    A[i] = can_reach(L[i], R[i], S[i], D[i]);

  for (int i = 0; i < Q; i++)
    if (A[i])
      printf("1\n");
    else
      printf("0\n");
  fclose(stdout);

  return 0;
}
#endif
/*
3 4
2 1 3
1 1 2 0
2
0 3 1 3
0 3 0 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: 17 / 17