제출 #1254986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254986		tosivanmak	장애물 (IOI25_obstacles)	C++20	0 / 100	56 ms	23876 KiB

obstacles

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

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';
        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(m+5),entering(m+5);

vector<bool>opened(m+5,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);
}
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>mini(n+5);
    for(int i=0;i<n;i++){
        mini[i]=T[i];
        if(i!=0){
            mini[i]=min(mini[i],mini[i-1]);
        }
    }
    for(int i=0;i<m;i++){
        ll l=0,r=n-1;
        if(mini[n-1]>H[i]){
            reachable[i]=n-1;
        }
        else if(mini[0]<=H[i]){
            reachable[i]=-1;
        }
        else{
            while(l<r){
                ll mid=(l+r+1)>>1;
                if(mini[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 maxi=-1;
    vector<pair<ll,ll> >rows;
    for(int i=0;i<n;i++){
        if(T[i]>maxi){
            rows.push_back({T[i],i}); maxi=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);
    //     }
    // }
}
bool can_reach(int L, int R, int S, int D){
    return d.connected(S,D);
}

#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: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17